-邻接点-

题目描述

一个有向图中有n个点（编号为1~n），e条边，请读入e条边，按照结点编号从小到大的顺序，输出每个点，及每个点的邻接点（有路径可到达的结点）有哪些（输出邻接点也按照编号从小到大的顺序）。
例如：有如下图所示的有向图

 

结点1的邻接点有：2 3 4
结点2的邻接点有：3 4
结点3的邻接点有：5
结点4的邻接点有：3 5
结点5没有邻接点

 

输入

第1行有2个整数，n和e，代表有n个点，e条边；（n≤1,000,000，e≤10,000）；
接下来e行，每行有2个整数x,y，代表x到y之间存在一有向条边（x,y≤n）
本题测试数据确保任意两点之间最多只有1条边、且数据合法，不存在x点到x点有边的情况。

输出

按照从小到大的顺序，先输出每个点的编号（如果该点没有出度，则该点不输出），再换行输出该点有出边可达的点的编号（也是按从小到大的顺序），输出格式请参考本题的样例。

样例输入

5 8
1 2
2 3
2 4
1 3
1 4
4 3
3 5
4 5

样例输出

1
2 3 4
2
3 4
3
5
4
3 5

提示

样例解释：
样例输入将形成如下图所示的图形，其中：
结点1的邻接点有：2 3 4
结点2的邻接点有：3 4
结点3的邻接点有：5
结点4的邻接点有：3 5
结点5没有邻接点，因此不输出



 

 参考代码：

#include
using namespace std;
int n,m,h[1000010],e[1000010],en[1000010],idx=1;
bool st[1000010];
struct node{
    int x,y;
}a[1000010];
void add(int a,int b){
    e[idx]=b;
    en[idx]=h[a];
    h[a]=idx++;
}
bool cmp1(node n1,node n2){
    if(n1.x!=n2.x)return n1.x     return n1.y>n2.y;
}
bool cmp2(node n1,node n2){
    if(n1.y!=n2.y)return n1.y     return n1.x>n2.x;
}
void dfs(int k){
    printf("%d\n",k);
    for(int i=h[k];i!=0;i=en[i]){
        int j=e[i];
        printf("%d ",j);
    }
    printf("\n");
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+m+1,cmp1);
    for(int i=1;i<=m;i++)
        add(a[i].x,a[i].y);
    for(int i=1;i<=n;i++)
        if(h[i]!=0)
            dfs(i);
    return 0;
}