P2002 消息扩散

思路：

根据题意，他说有环，自然想到要用tarjan,后面就很简单了；

缩完点之后重新建图，开一个inin数组表示该点的入度是多少（psps：该点表示缩完点之后的大点）；

最后统计一下那个点没有入度就好了；

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<stack>

using namespace std;
#define maxn 10101110

stack<int>q;

struct Node

{

    int next,to;

}e[maxn],ee[maxn];

int dfn[maxn],low[maxn],be[maxn];

int vis[maxn],in[maxn],headd[maxn];

int n,m,num,num1,ans,head[maxn];

//num1表示大点的个数，num表示tarjan中的编号

//head原图，e->原图；ee->新图 headd->新图

void add(int x,int y)

{

    e[++head[]].next=head[x];

    e[head[]].to=y;

    head[x]=head[];

}

void ad(int x,int y)

{

    ee[++headd[]].next=headd[x];

    ee[headd[]].to=y;

    headd[x]=headd[];

}

//这里我用的head[0]，headd[0]表示是为了节省一个小小的空间

void tarjan(int x)

{

    vis[x]=;q.push(x);

    dfn[x]=low[x]=++num;

    for(int i=head[x];i;i=e[i].next)

    {

        int t=e[i].to;

        if(!dfn[t])

        {

            tarjan(t);

            low[x]=min(low[x],low[t]);

        }

        else if(vis[t])

            low[x]=min(low[t],low[x]);

    }

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

    {

        vis[x]=;

        be[x]=++num1;

        while(q.top()!=x)

        {

            be[q.top()]=num1;

            vis[q.top()]=;

            q.pop();

        }

        be[q.top()]=num1;

        vis[q.top()]=;

        q.pop();

    }

}

int main()

{

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

    for(int i=;i<=m;i++)

    {

        int y,u;

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

        add(y,u);

    }//加边

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

        if(!dfn[i])

            tarjan(i);

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

        for(int j=head[i];j;j=e[j].next)

            if(be[i]!=be[e[j].to])

            {

                ad(be[i],be[e[j].to]);

                in[be[e[j].to]]++;

                //加新边同时记in

            }

    for(int i=;i<=num1;i++)

        if(!in[i])

            ans++;

    printf("%d",ans);

    return ;

}