Codeforces999E——Reachability from the Capital

There are n cities and m roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.
What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?
New roads will also be one-way.
Input
The first line of input consists of three integers n, m and s (1≤n≤5000,0≤m≤5000,1≤s≤n) — the number of cities, the number of roads and the index of the capital. Cities are indexed from 1 to n.
The following m lines contain roads: road i is given as a pair of cities ui, vi (1≤ui,vi≤n, ui≠vi). For each pair of cities (u,v), there can be at most one road from u to v. Roads in opposite directions between a pair of cities are allowed (i.e. from u to v and from v to u).
Output
Print one integer — the minimum number of extra roads needed to make all the cities reachable from city s. If all the cities are already reachable from s, print 0.
Examples
Input
9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1
Output
3
Input
5 4 5
1 2
2 3
3 4
4 1
Output
1
Note
The first example is illustrated by the following:
这里写图片描述
For example, you can add roads (6,4), (7,9), (1,7) to make all the cities reachable from s=1.
The second example is illustrated by the following:
这里写图片描述
In this example, you can add any one of the roads (5,1), (5,2), (5,3), (5,4) to make all the cities reachable from s=5.

这题是看了大佬的博客才大概有的思路
其实就是求一个有向图有多少个不同于capital点的根节点,因为只要从capital连一个到这些根节点,根节点以下的点也可以到达
所以就是用dfs来做
然后注意一个很重要的问题,环的问题,因为dfs是是循环进行的,也就是dfs(1,1) dfs(2,2) 这样,所以当有环的情况而且capital点不是1的话,他会在1的dfs时被记录,变成根节点是1,但其实这种含有capital点的环的根节点应该算capital点,所以在for循环之前要先dfs(s,s)

代码:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
using namespace std;
const int MAXN=5050;
int n,m,s;
int u,v;
//保存根节点
int fa[MAXN];
int vis[MAXN];
vector<int> G[MAXN];
set<int> res;
void dfs(int u,int f){
    //如果父亲节点已经是根节点
    if(fa[u]==f){
        return;
    }
    fa[u]=f;
    for(int i=0;i<G[u].size();i++){
        dfs(G[u][i],f);
    }
}
int main(void){
    scanf("%d%d%d",&n,&m,&s);
    while(m--){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    //先对起点dfs 比如环1-2-3-4-1 2为起点 如果不先dfs(2,2) 最终2的根节点记为1 而实际上要记为2
    dfs(s,s);
    //遍历一遍确定根节点
    for(int i=1;i<=n;i++){
        if(fa[i]==0){
            dfs(i,i);
        }
    }
    //标记s是否是根节点之一 如果是 则结果要减去1
    int flag=0;
    for(int i=1;i<=n;i++){
        //printf("%d ",fa[i]);
        if(fa[i]==s){
            flag=1;
        }
        res.insert(fa[i]);
    }
    //printf("\n");
    printf("%d\n",res.size()-flag);
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
06-02 15:53
阳光学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务