题目描述
There are nn cities and mm 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 nn, mm and ss (1≤n≤5000,0≤m≤5000,1≤s≤n1≤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 11 to nn.
The following mm lines contain roads: road ii is given as a pair of cities uiui, vivi (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi). For each pair of cities (u,v)(u,v), there can be at most one road from uu to vv. Roads in opposite directions between a pair of cities are allowed (i.e. from uu to vv and from vv to uu).
Output
Print one integer — the minimum number of extra roads needed to make all the cities reachable from city ss. If all the cities are already reachable from ss, 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
The first example is illustrated by the following:
For example, you can add roads (6,46,4), (7,97,9), (1,71,7) to make all the cities reachable from s=1s=1.
The second example is illustrated by the following:
In this example, you can add any one of the roads (5,15,1), (5,25,2), (5,35,3), (5,45,4) to make all the cities reachable from s=5s=5.
题解：
强连通缩点后统计入度为0的个数ans，然后看首都的入度是否为0；如果是则ans-1;
#include<cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
using namespace std; const int MAXN=1e5+;
const int inf=0x3f3f3f3f;
struct node{
int to;
int next;
}edge[MAXN*];
int head[MAXN];
int val[MAXN];
bool instack[MAXN];
int cnt;
int dfn[MAXN],low[MAXN];
int sum[MAXN];
void add(int x,int y)
{
edge[++cnt].to =y;
edge[cnt].next=head[x];
head[x]=cnt;
}
int Time,num;
stack<int >st;
int du[MAXN];
int color[MAXN];
int x[MAXN],y[MAXN];
void tarjan(int u)
{
dfn[u]=low[u]= ++Time;
st.push(u);
instack[u]=true;
for (int i = head[u]; i !=- ; i=edge[i].next) {
int v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
int x;
num++;
while() {
x=st.top();
st.pop();
color[x]=num;
instack[x]=false;
if(x==u) break;
} }
} int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
cnt=;
memset(head,-,sizeof(head));
memset(instack,false, sizeof(instack));
memset(sum, ,sizeof(sum));
for (int i = ; i <=m ; ++i) {
scanf("%d%d",&x[i],&y[i]);
add(x[i],y[i]);
}
for (int i = ; i <=n ; ++i) {
if(!dfn[i]) tarjan(i);
}
for (int i = ; i <=m ; ++i) {
if(color[x[i]]!=color[y[i]])
{
du[color[y[i]]]++;
}
} int ans=;
for (int i = ; i <=num ; ++i) {
if(du[i]==) ans++;
}
if(du[color[s]]==) ans--;
printf("%d\n",ans);
return ;
}