CodeForces 999E Reachability from the Capital

题目

◇题目传送门◆

题目大意

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

思路

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

然后就交给DFS了。

实现细节

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

若$S=2$，当我们按常规方法找出连通块，即按节点编号从小到大的顺序去遍历图，则我们可以得到连通块：$\{ 1,6\}$和$\{ 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 LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%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;
}