P3916 图的遍历(邻接表法)

void add(int x, int y) { // 添加条目
	nxt[++cnt] = header[x];
	data[cnt] = y;
	header[x] = cnt;
}
void dfs(int x) { // 深搜(倒着)
	ans[x] = maxn;
	for(int i = header[x]; i; i = nxt[i]) // 简洁
	    if(!ans[data[i]]) dfs(data[i]);
}

因为这题的范围很大，所以我们需要反向建表，即将深搜过程中每一个数都设为一开始进行深搜的最大的数。

cin >> x >> y;
add(y, x);

然后倒着进行dfs

for (int d1=n;d1>=1;d1--) {
    if (ans[d1]) continue; // TODO: 别忘记已经计算过的要跳过!!!!
    maxn = d1;
    dfs(d1);
}
for (int d1=1;d1<=n;d1++) {
   cout << ans[d1] << " ";
}