zoj_3795 Grouping

题目:

  Suppose there are N people in ZJU, whose ages are unknown. We have some messages about them. The i-th message shows that the age of person si is not smaller than the age of person ti. Now we need to divide all these N people into several groups. One's age shouldn't be compared with each other in the same group, directly or indirectly. And everyone should be assigned to one and only one group. The task is to calculate the minimum number of groups that meet the requirement.

思路:

  设为和有关的人的个数(包括自己),那么答案就是。对整幅图缩点,遍历一边得到的DAG上就能计算出了。

代码:

#include <bits/stdc++.h>
#define MN 100005
#define clr(a,b) memset(a,b,sizeof a)
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
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;}
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])
};
Link<MN,300005,int> G,M;
int dfn[MN],low[MN],ble[MN],siz[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(dfn[o]==low[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            siz[bcnt]++;
        }while(stk[tp--]!=o);
    }
}
int ind[MN],n;
void rebuild(){
    FOR(o,1,n)EOR(k,G,o){
        int v=G[k];
        if(ble[o]!=ble[v]){
            M.add(ble[o],ble[v]);
            ind[ble[v]]++;
        }
    }
}
int q[MN],val[MN];
int solve(){
    int hed=1,tai=0,ans=0;
    FOR(i,1,bcnt)if(!ind[i]){
        q[++tai]=i;
        val[i]=siz[i];
    }
    while(hed<=tai){
        int o=q[hed++];
        tomax(ans,val[o]);
        EOR(k,M,o){
            int v=M[k];
            tomax(val[v],val[o]+siz[v]);
            if(!--ind[v])q[++tai]=v;
        }
    }
    return ans;
}
void clear(){
    G.clear();M.clear();
    clr(dfn,0);clr(ble,0);
    clr(siz,0);clr(val,0);
    No=bcnt=0;
}
int main(){
    int m;
    while(~scanf("%d%d",&n,&m)){
        clear();
        for(int i=1,a,b;i<=m;i++){
            scanf("%d%d",&a,&b);
            G.add(a,b);
        }
        FOR(i,1,n)if(!dfn[i])
            dfs(i);
        rebuild();
        printf("%d\n",solve());
    }
    return 0;
}