hdu 3836 Equivalent Sets【强联通】

浏览数：34 / 时间：2015年06月11日

Equivalent Sets

Time Limit: 12000/4000 MS (Java/Others) Memory Limit: 104857/104857 K (Java/Others)
Total Submission(s): 3065 Accepted Submission(s): 1077

Problem Description

To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.

Input

The input file contains multiple test cases, in each case, the first line contains two integers N <= 20000 and M <= 50000.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.

Output

For each case, output a single integer: the minimum steps needed.

Sample Input

Sample Output

4
2
分析：题意：有1~N代表N个结论，首先已给出m个关系，a b 代表a能证明b，为至少需要添加几条边
     能是N条结论相互两两能够证明，很明显就是至少添加几条边使构成一个强联通。
     先缩点，在求出入度为0，和出度为0的个数，取其最大这便为答案。
#include<stdio.h>
#include<string.h>
//#include<algorithm>
//#include<iostream>
#include<stack>
#define Max(a,b) a>b?a:b
#define maxh 220000+10
#define maxn 550000+10
using namespace std;
typedef struct{
    int to,next;
}node;
stack<int>S;
node E1[maxn],E2[maxn];
int head1[maxh],head2[maxh],mark[maxh],cnt1,cnt2;
int belong[maxh],num[maxh][2],in[maxh],out[maxh],count;
void init(int n){
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    cnt1=0;
    cnt2=0;
}
void add(int a,int b){
    E1[cnt1].to=b,E1[cnt1].next=head1[a],head1[a]=cnt1++;
    E2[cnt2].to=a,E2[cnt2].next=head2[b],head2[b]=cnt2++;
}
void dfs1(int x){
    mark[x]=1;
    for(int i=head1[x];i+1;i=E1[i].next){
        int to=E1[i].to;
        if(mark[to])
        continue;
        dfs1(to);
    }
    S.push(x);
}
void dfs2(int x){
    mark[x]=1;
    belong[x]=count;
    for(int i=head2[x];i+1;i=E2[i].next){
        int to=E2[i].to;
        if(mark[to])
        continue;
        dfs2(to);
    }
}
int main(){
    int n,m,a,b,sumin,sumout;
    while(~scanf("%d%d",&n,&m)){
        init(n);
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            num[i][0]=a;
            num[i][1]=b;
            add(a,b);
        }
        memset(mark,0,sizeof(mark));
        while(!S.empty())
        S.pop();
        for(int i=1;i<=n;i++){
            if(!mark[i]){
                dfs1(i);
            }
        }
        memset(mark,0,sizeof(mark));
        count=0;
        while(!S.empty()){
            int s=S.top();
            S.pop();
            if(!mark[s]){
                count++;
                dfs2(s);
            }
        }
        if(count==1){
            printf("0\n");
            continue;
        }
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        sumin=sumout=0;
        for(int i=0;i<m;i++){
            if(belong[num[i][0]]!=belong[num[i][1]])
            in[belong[num[i][0]]]=out[belong[num[i][1]]]=1;
        }  
        for(int i=1;i<=count;i++){
            if(!in[i]){
                sumin++;
            }
            if(!out[i]){
                sumout++;
            }
        }
    printf("%d\n",Max(sumin,sumout));
    }
    return 0;
}