nyoj 120 校园网络

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=120

思路：先将原图强连通缩点为新图，统计新图中入度，出度为0的点的个数，两者取最大值即为答案。

代码如下：

#include "stdio.h"

#include "string.h"

#include "stack"

#include "vector"

using namespace std;

#define N 105

#define M 10005

struct node

{

    int x,y;

    int next;

}edge[2*M];

int idx,head[N];

void Init(){ idx=0; memset(head,-1,sizeof(head)); }

inline int MIN(int a,int b){ return a<b?a:b; }

inline int MAX(int a,int b){ return a>b?a:b; }

void Add(int x,int y)

{

    edge[idx].x=x;

    edge[idx].y=y;

    edge[idx].next=head[x];

    head[x]=idx++;

}

bool vis[N];

int dfn[N],low[N];

int dfs_clock;

int countt;

int belong[N];

stack<int> q;

void DFS(int x)   //强连通缩点算法

{

    int i,y;

    q.push(x);

    vis[x] = true;

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

    for(i=head[x]; i!=-1; i=edge[i].next)

    {

        y = edge[i].y;

        if(!dfn[y])

        {

            DFS(y);

            low[x] = MIN(low[x],low[y]);

        }

        else if(vis[y])

            low[x] = MIN(dfn[y],low[x]);

    }

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

    {

        int temp;

        countt++;

        while(1)

        {

            temp = q.top();

            q.pop();

            belong[temp] = countt;

            vis[temp] = false;

            if(temp==x) break;

        }

    }

}

int ru_du[N],chu_du[N];

int Solve(int n)

{

    int i;

    int x,y;

    dfs_clock = countt = 0;

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

    memset(vis,false,sizeof(vis));

    memset(belong,0,sizeof(belong));

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

    {

        if(!dfn[i])

            DFS(i);

    }

    if(countt==2) return 0;  //该图原本就是强连通图，return 0;

    memset(ru_du,0,sizeof(ru_du));

    memset(chu_du,0,sizeof(chu_du));

    for(i=0; i<idx; ++i)

    {

        x = belong[edge[i].x];

        y = belong[edge[i].y];

        if(x!=y)  //统计入度，出度

        {

            chu_du[x]++;

            ru_du[y]++;

        }

    }

    int ru_0=0,chu_0=0;

    for(i=1; i<countt; ++i)

    {

        if(ru_du[i]==0) ru_0++;

        if(chu_du[i]==0) chu_0++;

    }

    int ans = MAX(ru_0,chu_0); //return 入度，出度最大的那个数

    return ans;

}

int main()

{

    int T;

    int n;

    int i,k;

    scanf("%d",&T);

    while(T--)

    {

        Init();

        scanf("%d",&n);

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

        {

            while(scanf("%d",&k),k)

                Add(i,k);

        }

        printf("%d\n",Solve(n));

    }

    return 0;

}