hdu3836 Equivalent Sets

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=3836；

題意：大緻是給一個有向圖，問加幾條邊能成為強連通圖。

分析：先對此圖進行強連通分量求解，然後要縮點，千萬要記住縮完點之後要從新連結圖，連完之後就有有點沒有入度，有點沒有出度；但強連通圖内所有點都有入入度和出度，是以按缺失點增加一個出度或一個入度，最後一定是入度等于出度是以求解最大值即可，但有一點，強連通分量為1的時候不需增加邊（做完心好累）。

代碼：

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

long long V;                              //定點數
vector<long long> G[100050];               //正向建圖
vector<long long> rG[100050];              //反向建圖
vector<long long> vs;                     //周遊的順序
bool used[100050];
long long cmp[100050];                     //強連通分量的拓撲序
void add_edge(long long from,long long to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(long long v){
    long long i;
    used[v]=1;
    for(i=0;i<G[v].size();i++)
    if(!used[G[v][i]])
    dfs(G[v][i]);
    vs.push_back(v);
}
void rdfs(long long v,long long k){
    long long i;
    used[v]=1;
    cmp[v]=k;
    for(i=0;i<rG[v].size();i++)     //隻有強連通分量才不受反向建邊
    if(!used[rG[v][i]])             //的影響，是以找出強連通分量的
    rdfs(rG[v][i],k);               //同時，找出強連通分量的拓撲序
}
long long scc(){
    long long i,k;
    memset(used,0,sizeof(used));
    vs.clear();
    for(i=0;i<V;i++)
    if(!used[i])
    dfs(i);
    memset(used,0,sizeof(used));
    k=0;
    for(i=vs.size()-1;i>=0;i--)     //拓撲序最小的點在容器vs的最後面
    if(!used[vs[i]])
    rdfs(vs[i],k++);
    return k;
}
long long x[100500],y[100500];
int main(){
    while(scanf("%I64d",&V)!=EOF){
        long long m;
        scanf("%I64d",&m);
        for(long long i=0;i<V;i++){
            G[i].clear();
            rG[i].clear();
            cmp[i]=i;
        }
        for(long long i=0;i<m;i++){
            scanf("%I64d%I64d",&x[i],&y[i]);
            if(x[i]!=y[i])
            add_edge(x[i]-1,y[i]-1);
        }
        long long s=scc();
        for(long long i=0;i<V;i++){
            G[i].clear();
            rG[i].clear();
        }
        for(long long i=0;i<m;i++){
            if(cmp[x[i]-1]!=cmp[y[i]-1]){
                add_edge(cmp[x[i]-1],cmp[y[i]-1]);
            }
        }
        if(s==1){
            cout<<0<<endl;
            continue;
        }//強連通分量為1時
//        cout<<sum<<endl;
        long long sum1,sum2;
        sum1=sum2=0;
        for(int i=0;i<s;i++){
            if(G[i].size()==0)
            sum1++;
            if(rG[i].size()==0)
            sum2++;
        }
        cout<<max(sum1,sum2)<<endl;
    }
    return 0;
}