传统题 1000ms 128MiB

邻接表建图求邻接点

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

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

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

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

输入格式

第1行有2个整数,nnee,代表有nn个点,ee条边;

接下来ee行,每行有2个整数x,yx,y,代表xxyy之间存在一条有向边

本题测试数据确保任意两点之间最多只有1条边、且数据合法,不存在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

数据范围

  • n1,000,000n≤1,000,000
  • e10,000e≤10,000
  • x,ynx,y≤n

图论基础

未认领
状态
已结束
题目
12
开始时间
2024-4-21 0:00
截止时间
2024-5-31 23:59
可延期
24 小时