lightoj 1034【强连通+缩点】

思路：
缩点，计算入度为0点的个数即可；
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

struct asd{

    int to;

    int next;

};

asd q[N*4];

int head[N*4],tol;

int n,m;

int dfn[N];

int low[N];

int stap[N];

int in[N];

int vis[N];

int tp,p,cnt;

int kc[N],kr[N];

void add(int a,int b)

{

    q[tol].to=b;

    q[tol].next=head[a];

    head[a]=tol++;

}

void tarjan(int u)

{

    dfn[u]=low[u]=++tp;

    stap[++p]=u;

    vis[u]=1;

    for(int v=head[u];v!=-1;v=q[v].next)

    {

        int i=q[v].to;

        if(!dfn[i])

        {

            tarjan(i);

            low[u]=min(low[u],low[i]);

        }

        else if(vis[i])

            low[u]=min(low[u],dfn[i]);

    }

    if(dfn[u]==low[u])

    {

        cnt++;

        int temp;

        while(1)

        {

            temp=stap[p];

            vis[temp]=0;

            in[temp]=cnt;

            p--;

            if(temp==u)

                break;

        }

    }

}

int fun()

{

    memset(kc,0,sizeof(kc));

    for(int i=1;i<=n;i++)

    {

        for(int v=head[i];v!=-1;v=q[v].next)

        {

            int to=q[v].to;

            if(in[to]!=in[i])

            {

                kc[in[to]]++;

            }

        }

    }

    int ans=0;

    for(int i=1;i<=cnt;i++)

    {

        if(!kc[i])

            ans++;

    }

    return ans;

}

int main()

{

    int T,cas=1,x,y;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        tol=0;

        memset(head,-1,sizeof(head));

        memset(dfn,0,sizeof(dfn));

        memset(vis,0,sizeof(vis));

        while(m--)

        {

            scanf("%d%d",&x,&y);

            add(x,y);

        }

        tp=p=cnt=0;

        for(int i=1;i<=n;i++)

        {

            if(!dfn[i])

                tarjan(i);

        }

        printf("Case %d: %d\n",cas++,fun());

    }

    return 0;

}
巴特西

lightoj 1034【强连通+缩点】

最新文章

热门文章
