题目描述
输入
4 3
1 2
2 4
4 3
输出
4 4 3 4
思路:DFS+构建反向图 如果仅仅使用DFS,从前往后进行搜索,每到一个新的节点就进行判断,然后更新标记,由于数据量较大,且每个节点能到达编号最大的点未知,所以可能会超时.我们想到了使用反向图.对于原来的图建立反向图,然后从最大编号的点开始进行DFS,起始点能到达的所有点,反过来也都能到达起始点.在进行DFS时,如果某点已经更新过了,则进行判断时则不用再进行判断,因为先标记的编号必然比后标记的大.这样一次DFS便可对多个点的最大能到达编号进行更新.
参考代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
int n, m, cnt, head[maxn], x, y;
int book[maxn];
struct Node {
int to, next;
}edge[maxn];
void add(int u, int v) {
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int u, int v) {
//u :从u开始 v:能到达的点
if (book[u]) {
return;
}
book[u] = v;
for (int e = head[u]; e != -1; e = edge[e].next) {
dfs(edge[e].to, v);
}
}
int main() {
cin >> n >> m;
memset(head, -1, sizeof(head));
for (int i = 1; i <= m; i++) {
cin >> x >> y;
add(y, x);//建立x->y的反向边--- y-->x
}
for (int i = n; i >= 1; i--) {
dfs(i, i);
}
for (int i = 1; i <= n; i++) {
if (i == 1) {
cout << book[i];
}
else {
cout << " " << book[i];
}
}
cout << endl;
return 0;
}