POJ1236学校网络——tarjan

题目：http://poj.org/problem?id=1236

Tarjan+缩点。温习一下Tarjan的写法。

1.在缩点后的TAG中，有几个联通块等价于有几个入度为0的点！

2.把它们都联通相当于给每个入度为0的点都连一条入边，给每个出度为0的点都连一条出边，所以二者取max即可。

* 有向图是强联通分量的充要条件是没有入度为0的点也没有出度为0的点。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=;

int n,head[N],rd[N],cd[N],dfn[N],low[N],xnt,cnt,tim;

int stack[N],top,r,c,col[N],ans,rrd[N];

bool in[N];

struct Edge{

    int next,from,to;

    Edge(int n=,int f=,int t=):next(n),from(f),to(t) {}

}edge[N*N];

void tarjan(int cur)

{

    dfn[cur]=low[cur]=++tim;

    stack[++top]=cur;in[cur]=;

    for(int i=head[cur],v;i;i=edge[i].next)

    {

        if(in[v=edge[i].to])

            low[cur]=min(low[cur],dfn[v]);

        else if(!dfn[v])tarjan(v),low[cur]=min(low[cur],low[v]);

    }

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

    {

        cnt++;

        while(cur!=stack[top])in[stack[top]]=,col[stack[top--]]=cnt;

        in[stack[top]]=;col[stack[top--]]=cnt;

    }

}

int main()

{

    scanf("%d",&n);int x;

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

        while()

        {

            scanf("%d",&x);if(!x)break;

            edge[++xnt]=Edge(head[i],i,x);head[i]=xnt;

        }

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

        if(!dfn[i])tarjan(i);//!dfn[i]

    for(int i=,v,u;i<=xnt;i++)

        if(col[u=edge[i].from]!=col[v=edge[i].to])rd[col[v]]++,cd[col[u]]++;

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

    {

        if(!rd[i])r++;if(!cd[i])c++;

    }

    if(cnt==)//

    {

        printf("1\n0");return ;

    }

    printf("%d\n%d",r,max(r,c));

    return ;

}