HDU2767Proving Equivalences tarjan缩点，如何求入度和出度最大值

　　给定一个有向图，问最少增加多少条边后变成强连通图
  　  tarjan求求强连通分量并缩点，如果强连通分量个数为1，则需要边数为0，
 　　否则为缩点后点入度和出度的最大值，
 　　证明：当入度或者出度不为0时，则可以通过传递性使其相同，所以只需要考虑入度或者出度为0的点
　　 即可。因为要求增加尽量少的边，所以将入度和出度都为0的点相连，边的方向为出度为0的指向入度为0的顶点。
　　 当入度为0或者出度为0的点有剩余时，则任意取一个点进行连边。
  　 所以当有向图为强连通图时答案为0，否则最小值为入度和入度的最大值

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 20005;

const int maxm = 100005;

struct node{

    int v,next;

}edge[maxm];

int head[maxn],low[maxn],dfn[maxn],sta[maxn],in[maxn],out[maxn],belong[maxn],vis[maxm];

int Time,id,top,num,total;

void add_edge(int u,int v){

    edge[id].v = v;edge[id].next = head[u];head[u] = id++;

}

void tarjan(int u){

    low[u] = dfn[u] = ++Time;

    sta[top++] = u;in[u] = 1;

    for(int id = head[u]; id != -1; id = edge[id].next){

        int v = edge[id].v;

        if(!dfn[v]){

            tarjan(v);

            if( low[u] < low[v])total++;

            low[u] = min(low[u],low[v]);

        }

        else if( in[v] )low[u] = min(low[u],low[v]);

    }

    if( low[u] == dfn[u]){

        num ++;

        do{

            int t = sta[--top];

            in[t] = 0;

            belong[t] = num;

        }while( sta[top] != u);

    }

}

int main(){

    int t;

    int n,m;

    int u,v;

    int cnt;

    scanf("%d",&t);

    while( t-- ){

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

        memset(head,-1,sizeof(head)),id = 0;

        while( m-- ){

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

            add_edge(u,v);

        }

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

        Time = num = total = cnt = 0;

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

            if(!dfn[i])

                tarjan(i);

        }

        if( num == 1){puts("0");continue;}

        memset(in,0,sizeof(in));

        memset(out,0,sizeof(out));

        for(int u = 1; u <= n; u++){

            for(int id = head[u]; id != -1; id = edge[id].next){

                int v = edge[id].v;

                if( belong[u] != belong[v]){

                    in[belong[v]]++;out[belong[u]]++;

                }

            }

        }

        int indeg = 0,outdeg = 0;

        for(int i = 1; i <= num; i++){

            if( !in[i])indeg ++;

            if( !out[i])outdeg++;

        }

        printf("%d\n",indeg > outdeg ? indeg : outdeg);

    }

    return 0;

}