给出 \(N\) 个点,\(M\) 条边的有向图,对于每个点 \(v\),求 \(A(v)\) 表示从点 \(v\) 出发,能到达的编号最大的点。
这题有一个巧妙思路,构造反图,把依次找每个能到达的最大的点,转化为从大到小枚举每个点搜索当前点能到达的所有点,第一次找到的点一定是最大点。
反图思路就是建每一条有向边的反向边。这种思想很重要
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m;
vector<int>e[N];
int ans[N];
int f;
void dfs(int u)
{
if (ans[u]) {
return;
}
ans[u] = f;
for (int v : e[u]) {
dfs(v);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0, a, b; i < m; i++) {
scanf("%d%d", &a, &b);
// opposite edge
e[b].push_back(a);
}
for (int i = n; i >= 1; i--) {
if (!ans[i]) {
f = i;
dfs(i);
}
}
for (int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
printf("\n");
return 0;
}
标签:遍历,int,d%,dfs,P3916,ans,反图
From: https://www.cnblogs.com/CYLSY/p/17080330.html