学步园

/****************************************************
算法引入:
在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通;
如果有向图G的每两个顶点都强连通,称G是一个强连通图;
非强连通图有向图的极大强连通子图,称为强连通分量;

算法介绍：
Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树;
搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量;

定义dfn(u)为节点u搜索的次序编号(时间戳),low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号;
则当dfn(u)=low(u)时,以u为根的搜索子树上所有节点是一个强连通分量;

Tarjan算法过程中,每个顶点都被访问了一次,且只进出了一次堆栈,每条边也只被访问了一次,则该算法的时间复杂度为O(N+M);

算法伪代码：
(1)找一个没有被访问过的节点v;否则算法结束;
(2)初始化dfn[v]和low[v];
对于v所有的邻接顶点u:
①如果没有被访问过,则转到步骤②,同时维护low[v];
②如果被访问过,但没有删除,维护low[v];
如果low[v]==dfn[v],那么输出相应的强连通分量;

算法举例:
HDU2767(Proving Equivalences);

题目大意:
求在图中添加多少条边能使图强连通;

算法思想:
首先用Tarjan算法求出图中强连通分量,然后缩点,统计缩点后的图的出入度;
最后答案是入度为0的点和出度为0的点中数量最大的;
*****************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int N=50050;

struct Node
{
    int to;
    int next;
};

Node Edge[N];
int head[N];
int flag[N],dfn[N],low[N];
int sum,top,stack[N];
int in[N],out[N],Dindex;
int n,m,cnt;

inline void Add_Edge(int u,int v)
{
    Edge[cnt].to=v;
    Edge[cnt].next=head[u];
    head[u]=cnt;
    cnt++;
}

int dfs(int s)
{
    flag[s]=1;
    low[s]=dfn[s]=Dindex++;
    stack[++top]=s;
    for(int i=head[s]; i!=-1; i=Edge[i].next)
    {
        if(flag[Edge[i].to]==0)
            dfs(Edge[i].to);
        if(flag[Edge[i].to]==1)
            low[s]=min(low[Edge[i].to],low[s]);
    }
    if(dfn[s]==low[s])
    {
        ++sum;
        do
        {
            low[stack[top]]=sum;
            flag[stack[top]]=2;
        }
        while(stack[top--]!=s);
    }
    return 0;
}

int Tarjan()
{
    sum=top=0;
    Dindex=1;
    memset(flag,0,sizeof(flag));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    for(int i=1; i<=n; i++)
    {
        if(flag[i]==0)
            dfs(i);
    }
    if(sum==1)
        return 0;
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    for(int i=1; i<=n; i++)
    {
        for(int j=head[i]; j!=-1; j=Edge[j].next)
        {
            if(low[Edge[j].to]!=low[i])
            {
                out[low[i]]++;
                in[low[Edge[j].to]]++;
            }
        }
    }
    int sum1=0,sum2=0;
    for(int i=1; i<=sum; i++)
    {
       // printf("in[%d]=%d,out[%d]=%d\n",i,in[i],i,out[i]);
        if(in[i]==0)
            sum1++;
        if(out[i]==0)
            sum2++;
    }
    return max(sum1,sum2);
}

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0; i<m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            Add_Edge(u,v);
        }
        printf("%d\n",Tarjan());
    }
    return 0;
}