2080 - 邻接点

题目描述

一个有向图中有 nn 个点(编号为 1n1 \sim n ),ee 条边,请读入 ee 条边,按照结点编号从小到大的顺序,输出每个点,及每个点的邻接点(有路径可到达的结点)有哪些(输出邻接点也按照编号从小到大的顺序)。

例如:有如下图所示的有向图

结点 11 的邻接点有:22 33 44

结点 22 的邻接点有:33 44

结点 33 的邻接点有:55

结点 44 的邻接点有:33 55

结点 55 没有邻接点。

输入

11 行有 22 个整数,nnee ,代表有 nn 个点, ee 条边;(n1,000,000n \le 1,000,000e10,000e \le 10,000);

接下来 ee 行,每行有 22 个整数 x,yx,y ,代表 xxyy 之间存在一有向条边(x,ynx,y \le n

本题测试数据确保任意两点之间最多只有 11 条边、且数据合法,不存在 xx 点到 xx 点有边的情况。

输出

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

样例

输入
复制

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没有邻接点,因此不输出


来源

图论 邻接表

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题