学步园

/**
[图论] hdu 3836 Equivalent Sets
求一个图中至少添加几条边成为强连通。
跑一遍tarjan缩点,统计0出度和0入度的点数x,y，则ans = max(x,y)
*/
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 20002

vector<int> vec[N];
int stop,cnt,scnt,id[N],pre[N],low[N],s[N],in[N],out[N];

void tarjan(int v,int n)
{
    int t,minc = low[v] = pre[v] = cnt++;
    vector<int>::iterator pv;
    s[stop++] = v;
    for(pv =  vec[v].begin(); pv != vec[v].end(); ++pv)
    {
        if(-1 == pre[*pv])
            tarjan(*pv,n);
        if(low[*pv] < minc)
            minc = low[*pv];
    }
    if(minc < low[v])
    {
        low[v] = minc;
        return ;
    }
    do{
        id[t = s[--stop] ]  = scnt;
        low[t] = n;
    }while(t != v);
    ++scnt;
}
int main()
{
    int k,n,m,i,j;
    while(scanf("%d%d",&n,&m) == 2)
    {
        for(i = 0; i < n; ++i)
            vec[i].clear();
        while(m--)
        {
            scanf("%d%d",&i,&j);
            --i;--j;
            vec[i].push_back(j);
        }
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(pre,-1,sizeof(pre));
        stop = cnt = scnt = 0;

        for(i = 0; i < n; ++i)
            if(-1 == pre[i])
                tarjan(i,n);

        for(i = 0; i < n; ++i)
        {
            for(j = 0; j < vec[i].size(); ++j)
                if(id[i] != id[vec[i][j]])
                {
                    in[id[vec[i][j]]] ++;
                    out[id[i]] ++;
                }
        }
        for(k = i = j = 0; k < scnt; ++k)
        {
            if(in[k] == 0)
                ++i;
            if(out[k] == 0)
                ++j;
        }
        if(scnt == 1)
            printf("0\n");
        else
            printf("%d\n",max(i,j));
    }
    return 0;
}