hdu_3836 Equivalent Sets

题目:

  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.

思路:

  假设给定的图是DAG,如果点的个数为,答案就等于。其他情况:设有个点入度为个点出度为。当时,这幅图是一整个联通块,因为每一条边可以消去一对出入度为的点,所以答案就是。给定的图不一定是DAG,只要缩点就好了。

代码:

#include <bits/stdc++.h>
#define MN 20005
#define clr(a,b) memset(a,b,sizeof a)
using namespace std;
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
Link<MN,50005,int> G;
int cnt[MN],ble[MN],dfn[MN],low[MN],stk[MN],tp,No,bcnt;
void dfs(int o){
    dfn[o]=low[o]=++No;
    stk[++tp]=o;
    EOR(k,G,o){
        int v=G[k];
        if(!dfn[v]){
            dfs(v);
            tomin(low[o],low[v]);
        }
        else if(!ble[v])tomin(low[o],dfn[v]);
    }
    if(low[o]==dfn[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            cnt[bcnt]++;
        }while(stk[tp--]!=o);
    }
}
int ind[MN],outd[MN],n;
void rebuild(){
    clr(ind,0);clr(outd,0);
    for(int i=1;i<=n;i++)
        EOR(k,G,i)
            if(ble[i]!=ble[G[k]])
                outd[ble[i]]++,ind[ble[G[k]]]++;
}
int main(){
    int m;
    while(~scanf("%d%d",&n,&m)){
        G.clear();clr(dfn,0);clr(ble,0);No=0;bcnt=0;
        for(int i=1,a,b;i<=m;i++){
            scanf("%d%d",&a,&b);
            G.add(a,b);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])dfs(i);
        rebuild();
        int ans1=0,ans2=0;
        for(int i=1;i<=bcnt;i++){
            if(!ind[i])ans1++;
            if(!outd[i])ans2++;
        }
        printf("%d\n",bcnt==1?0:max(ans1,ans2));
    }
    return 0;
}