题目描述

输入

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