2080: 【入门】邻接点
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:40
解决:20
题目描述
一个有向图中有n个点(编号为1~n),e条边,请读入e条边,按照结点编号从小到大的顺序,输出每个点,及每个点的邻接点(有路径可到达的结点)有哪些(输出邻接点也按照编号从小到大的顺序)。
例如:有如下图所示的有向图
结点1的邻接点有:2 3 4
结点2的邻接点有:3 4
结点3的邻接点有:5
结点4的邻接点有:3 5
结点5没有邻接点
例如:有如下图所示的有向图
结点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点有边的情况。
接下来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没有邻接点,因此不输出
注:此题可使用链式前向星加边方式,防止超时。
样例输入将形成如下图所示的图形,其中:
结点1的邻接点有:2 3 4
结点2的邻接点有:3 4
结点3的邻接点有:5
结点4的邻接点有:3 5
结点5没有邻接点,因此不输出
注:此题可使用链式前向星加边方式,防止超时。