【CodeForces】【搜索】999E Reachability from the Capital

CodeForces 999E Reachability from the Capital

题目

◇题目传送门◆

题目大意

给定三个正整数N$N$，M$M$，S$S$，N$N$表示图中一共有N$N$个节点，M$M$表示有M$M$条边，S$S$是N$N$个节点中的一个，并给定M$M$条单向边，求至少需要加几条单向边，使得从S$S$出发，能够到达所有其他节点。

思路

一看就是一个求连通块的变形问题。

然后就交给DFS了。

实现细节

注意：可能会出现如下一种情况：（灵魂画手就是我）

若S=2$S=2$，当我们按常规方法找出连通块，即按节点编号从小到大的顺序去遍历图，则我们可以得到连通块：{1,6}$\{1,6\}$和{2,5,4,3}$\{2,5,4,3\}$，但实际上，这里只有一个连通块！
所以，我们应允许改变每个节点的连通分量！

注意：由于上面这种方法，我们在输出答案时应计算出有多少不同的连通分量，答案即将它减一（极易用贪心方法说明）。

正解代码

#include<cstdio>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int Maxn=5000;
int N,M,S;

vector<int> G[Maxn+5];
void AddEdge(int u,int v) {
    G[u].push_back(v);
}

int vis[Maxn+5];
int cnt;
void DFS(int u) {
    vis[u]=cnt;
    for(int i=0;i<G[u].size();i++) {
        int v=G[u][i];
        if(vis[v]==cnt||v==S)continue;
        DFS(v);
    }
}

set<int> tmp;
int GetAns() {
    for(int i=1;i<=N;i++)
        tmp.insert(vis[i]);
    return tmp.size()-1;
}

int main() {
    #ifdef LOACL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    scanf("%d %d %d",&N,&M,&S);
    for(int i=1;i<=M;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        AddEdge(u,v);
    }

    cnt=1;DFS(S);

    for(int i=1;i<=N;i++)
        if(!vis[i]) {
            cnt++;
            DFS(i);
        }

    printf("%d\n",GetAns());
    return 0;
}