POJ 1236 Network of Schools強連通分量縮點

/*相當經典的題目了. 題的描述有點兒長, 我就不想再描述了...
題中的任務A, 其本質就是求這個有向圖中所有強連通分量中, 入度為0的個數. 原理還是挺好了解的:
入度不為0的強連通分量, 顯然可以由其他強連通分量達到. 也就是說, 要想讓所有學校都拿到軟體,
需要且隻需要從入度為0的那些強連通分量出發即可.
題中的任務B稍微複雜些., 意思是增加多少條邊, 可以使整個圖變成強連通的. 這時需要分别統計入度
為0和出度為0的點, 設它們的個數分别是a, b. 首先, 我們可以在入度為0和出度為0的點之間連邊. 之後,
如果入度 / 出度為0的點有剩餘, 就把它們和其他點連邊. 是以, 需要連的邊條數為 max(a, b).
隻有一個聯通塊的時候，輸出零。因為不需要添加邊
*/
#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 105
#define maxm 3000
int top;//棧頂位置
int Bcnt;//強連通分量編号
int Index;//時間順序
int DFN[maxn];//時間戳
int LOW[maxn];
int belong[maxn];//頂點i屬于哪個強連通分量
int Stack[maxn];//棧
int instack[maxn];//是否在棧内
int n, m;
struct node
{
    int to;
    int next;
} edge[maxm];
int head[maxn];
bool Judge[maxn];
bool Judge2[maxn];
int ansi;
void init()
{
    fill(head, head + n + 1, -1);
    fill(DFN, DFN + n + 1, 0);
    fill(Judge, Judge + n + 1, true);
    fill(Judge2, Judge2 + n + 1, true);
    ansi = 0;
    top = 0;
    Bcnt = 0;
    Index = 0;
}
void add(int a, int b)
{
    edge[ansi].to = b;
    edge[ansi].next = head[a];
    head[a] = ansi++;
}
void read()
{
    int a;
    for (int i = 1; i <= n; i++)
    {
        while (scanf("%d", &a) && a)
            add(i, a);
    }
}
void tarjan(int i)
{
    int j, k;
    DFN[i] = LOW[i] = ++Index;
    instack[i] = true;
    top++;
    Stack[top] = i;
    for (k = head[i]; k != -1; k = edge[k].next)
    {
        j = edge[k].to;
        if (!DFN[j])//j未通路，用dfn值标記是否已通路過
        {
            tarjan(j);
            if (LOW[j] < LOW[i])
                LOW[i] = LOW[j];
        }
        else if (instack[j] && DFN[j] < LOW[i])
            LOW[i] = DFN[j];
    }
    if (DFN[i] == LOW[i]) //dfn和low相等，遞歸列印強連通分量
    {
        Bcnt++;//強連通分量編号
        do
        {
            j = Stack[top--];
            instack[j] = false;
            belong[j] = Bcnt;
        }
        while (j != i);
    }
}
void judge1()
{
    for (int i = 1; i <= n; i++)
        for (int k = head[i]; k != -1; k = edge[k].next)
        {
            if (belong[i] != belong[edge[k].to])
                Judge[belong[i]] = false;
        }
}
void judge2()
{
    for (int i = 1; i <= n; i++)
        for (int k = head[i]; k != -1; k = edge[k].next)
        {
            if (belong[i] != belong[edge[k].to])
                Judge2[belong[edge[k].to]] =false;
        }
}
void solve()
{
    init();
    read();
    for (int i = 1; i <= n; i++)
        if (!DFN[i])
            tarjan(i);
    judge1();
    judge2();
    int s1=0;//所有出度為零的
    int s2=0;//所有入度為零的
    for (int i = 1; i<=Bcnt; i++)
    {
        if (Judge[i])s1++;
        if(Judge2[i])s2++;
    }
    printf("%d\n",s2);
    int ss;
    if(Bcnt==1)ss=0;
    else ss=max(s1,s2);
    printf("%d\n",ss);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d", &n) != EOF)
    {
        solve();
    }
}