CodeForces ~ 999E ~ Reachability from the Capital (思维 + 图的DFS)
程序员文章站
2022-05-15 14:02:46
...
题意:
n个点(1~n),m条单向边,s为起点,然后输入这m条边。问最少在增加多少条单向边,可以使s可以到达各个点?
思路:
dfs所有点,并记录他们的根节点。最终有x个根节点,有两种情况:
①s不为根节点,那么就需要增加x条边。
②s为一个根节点,那就需要增加x-1条边
注意,可能有环的情况,环的情况我们可以以任意点作为根节点,假设s在某个环中,而我们没以s作为根节点,那么求出来的值就会比答案大一。所以在dfs所有点之前,先dfs起点一次。
最下面给了一张图,帮助理解。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int n, m, s, f[MAXN], vis[MAXN];
vector<int> G[MAXN];
void dfs(int u, int fa)
{
if (f[u] == fa) return ;
f[u] = fa;
for (auto i: G[u])
dfs(i, fa);
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 0; i < m; i++)
{
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
}
dfs(s, s);
for (int i = 1; i <= n; i++) if (!f[i])
dfs(i, i);
int ans = 0;
for (int i = 1; i <= n; i++) if (!vis[f[i]])
vis[f[i]] = 1, ans++;
printf("%d\n", ans-vis[s]);
return 0;
}
/*
9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1
*/
推荐阅读
-
【CodeForces】【搜索】999E Reachability from the Capital
-
codeforces 999E Reachability from the Capital targan+缩点
-
CodeForces ~ 999E ~ Reachability from the Capital (思维 + 图的DFS)
-
Codeforces Round #490 (Div. 3) E. Reachability from the Capital(tarjan+连通图)
-
999E - Reachability from the Capital(Codeforces Round #490 (Div. 3))