输入
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; }
