Reachability from the Capital

题目描述

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.

#include
#include 
#include 
#include 
#include using namespace std;

const int MAXN=1e5+10;
const int inf=0x3f3f3f3f;
struct node{
    int to;
    int next;
}edge[MAXN*4];
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;
stackint >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 !=-1 ; 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(1) {
            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=0;
    memset(head,-1,sizeof(head));
    memset(instack,false, sizeof(instack));
    memset(sum, 0,sizeof(sum));
    for (int i = 1; i i) {
        scanf("%d%d",&x[i],&y[i]);
        add(x[i],y[i]);
    }
    for (int i = 1; i i) {
        if(!dfn[i]) tarjan(i);
    }
    for (int i = 1; i i) {
        if(color[x[i]]!=color[y[i]])
        {
            du[color[y[i]]]++;
        }
    }

    int ans=0;
    for (int i = 1; i i) {
        if(du[i]==0) ans++;
    }
    if(du[color[s]]==0) ans--;
    printf("%d\n",ans);
    return 0;
}