本文共 1988 字，大约阅读时间需要 6 分钟。
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 11 21 32 31 55 66 11 89 87 1
Output
3
Input
5 4 51 22 33 44 1
Output
1
Note
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 .
题意：
给出一幅图， 求再加几条边能够使首都都能够到达所有城市。 。。先用targan+ 缩点， 将所有的连通分量缩成一个点， 统计除了首都所在的缩点入度为0的个数。 。
代码如下：
#include#include #include #include #include #include using namespace std;const int maxn=5e3+5;vector ve[maxn];int ccnc[maxn],in[maxn];stack s;int n,m,ss;int low[maxn],dfn[maxn];int tot,ccnum,sum=0;void init(){ ccnum=tot=0; memset (in,0,sizeof (in)); memset (low,0,sizeof(low)); memset (dfn,0,sizeof(dfn)); memset (ccnc,0,sizeof(ccnc));}void targan (int x){ low[x]=dfn[x]=++tot; s.push(x); for (int i=0;i
转载地址：http://ktaen.baihongyu.com/