测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A70736. 邻接点

编程题 入门

题目描述

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

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

结点 1 的邻接点有:2 3 4

结点 2 的邻接点有:3 4

结点 3 的邻接点有:5

结点 4 的邻接点有:3 5

结点 5 没有邻接点。

输入格式

1 行有 2 个整数,ne ,代表有 n 个点, e 条边;(n \le 1,000,000e \le 10,000);

接下来 e 行,每行有 2 个整数 x,y ,代表 xy 之间存在一有向条边(x,y \le n

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

输出格式

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

输入输出样例

输入 #1
5 8
1 2
2 3
2 4
1 3
1 4
4 3
3 5
4 5
输出 #1
1
2 3 4
2
3 4
3
5
4
3 5

说明/提示

## 思路

「邻接点」先建图再遍历或求特殊路径。

## 步骤

1. 读入点数边数并建邻接表。
2. 按题意 DFS/BFS 或求最短路、欧拉路。
3. 输出路径或距离。