图的遍历
题目描述
给出 个点，
条边的有向图，对于每个点
，求
表示从点
出发，能到达的编号最大的点。
输入格式
第 行
个整数
，表示点数和边数。
接下来 行，每行
个整数
，表示边
。点用
编号。
输出格式
一行 个整数
。
样例 #1
样例输入 #1
4 3
1 2
2 4
4 3样例输出 #1
4 4 3 4提示
- 对于
的数据，
。
- 对于
的数据，
。
思路
储存图时反向存储，即将边的起点和终点对调。然后从最大编号的节点开始对图进行反向遍历，所能到达的节点的所求值即起点的值。
AC代码
#include <iostream>
#include <cstring>
using namespace std;
#define AUTHOR "HEX9CF"
const int maxn = 100005;
int cnt = 0;
int maxi[maxn];
// 链式前向星
struct Sedge
{
int to;
int next;
} edge[maxn];
int head[maxn];
void add(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int x, int ori)
{
if (maxi[x])
{
return;
}
maxi[x] = ori;
for (int i = head[x]; ~i; i = edge[i].next)
{
dfs(edge[i].to, ori);
}
}
void read(int &x)
{
char ch;
x = 0;
while (!('0' <= ch && '9' >= ch))
{
ch = getchar();
}
while (('0' <= ch && '9' >= ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
}
int main()
{
int n, m;
int a, b;
memset(head, -1, sizeof(head));
memset(maxi, 0, sizeof(maxi));
read(n);
read(m);
for (int i = 1; i <= m; i++)
{
read(a);
read(b);
add(b, a); // 反向添加边
}
for (int i = n; i; i--)
{
// 反向搜索
dfs(i, i);
}
for (int i = 1; i <= n; i++)
{
cout << maxi[i];
if (i != n)
{
cout << " ";
}
}
return 0;
}