欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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 (思维 + 图的DFS)