Reachability from the Capital

发布时间：2020-12-14 03:20:26 所属栏目：大数据来源：网络整理

导读：题目描述 There are? n n?cities and? m m?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 capita

There are? $n$

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? $n$

The following? $m$

Output

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city? $s$

Examples

Input

Output

Input

Output

The first example is illustrated by the following:

For example,you can add roads ( $6, 4$

The second example is illustrated by the following:

In this example,you can add any one of the roads ( $5, 1$

题解：?

强连通缩点后统计入度为0的个数ans，然后看首都的入度是否为0；如果是则ans-1;

#include<cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
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;
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 !=-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 <=m ; ++i) {
        scanf("%d%d",&x[i],&y[i]);
        add(x[i],y[i]);
    }
    for (int i = 1; i <=n ; ++i) {
        if(!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <=m ; ++i) {
        if(color[x[i]]!=color[y[i]])
        {
            du[color[y[i]]]++;
        }
    }

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!