欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces 999E Reachability from the Capital targan+缩点

程序员文章站 2022-05-15 14:02:52
...

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

Note

The first example is illustrated by the following:

codeforces 999E Reachability from the Capital targan+缩点

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:

codeforces 999E Reachability from the Capital targan+缩点

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int maxn=5e3+5;
vector<int>ve[maxn];
int ccnc[maxn],in[maxn];
stack<int>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<ve[x].size();i++)
    {
        int v=ve[x][i];
        if(!dfn[v])
        {
            targan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(!ccnc[v])
            low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        ccnum++;
        while (1)
        {
           int now=s.top();
           s.pop();
           ccnc[now]=ccnum;
           if(now==x)
              break;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&ss);
    init();
    while (m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ve[x].push_back(y);
    }
    for (int i=1;i<=n;i++)
        if(!dfn[i])
             targan(i);
    for (int i=1;i<=n;i++)
       for (int j=0;j<ve[i].size();j++)
       {
            int v=ve[i][j];
            if(ccnc[i]!=ccnc[v])
                 in[ccnc[v]]++;
       }
    int temp=ccnc[ss];
    for (int i=1;i<=ccnum;i++)
    {
         if(!in[i]&&i!=temp)
              sum++;
    }
    printf("%d\n",sum);
    return 0;
}