2018-team4-modules-支配树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct Graph{
    struct Edge{
        int to,next;
    }G[maxm];
    int head[maxn],cnt;
    void clear(){
        memset(head,0,sizeof head);
        cnt = 0;
    }
    void add(int u,int v){
        G[++cnt].to = v;
        G[cnt].next = head[u];
        head[u] = cnt;
    }
}ori,inv,nwg;
int ufa[maxn],pos[maxn],ido[maxn],sdo[maxn];
int find(int x){
    if(x == ufa[x]) return ufa[x];
    int r = find(ufa[x]);
    if(sdo[pos[ufa[x]]] < sdo[pos[x]]) pos[x] = pos[ufa[x]];
    return (ufa[x] = r);
}
inline int eval(int x){
    find(x);return pos[x];
}
int n,m,dfn[maxn],seq[maxn],dfs_clock;
int fa[maxn];
void dfs(int u){
    dfn[u] = ++ dfs_clock;
    seq[dfs_clock] = u;
    sdo[u] = dfs_clock;
    for(int i = ori.head[u],v;i;i = ori.G[i].next){
        v = ori.G[i].to;
        if(dfn[v]) continue;
        fa[v] = u;
        dfs(v);
    }
}
vector<int>ve[maxn];
int main(){
    while(scanf("%d%d",&n,&m) != EOF){
        rep(i,1,n) ufa[i] = i,pos[i] = i;
        ori.clear();inv.clear();nwg.clear();
        rep(i,1,n) ve[i].clear(),dfn[i] = seq[i] = ido[i] = sdo[i] = sum[i] = fa[i] = 0;
        dfs_clock = 0;
        int u,v;
        rep(i,1,m){
            read(u);read(v);
            ori.add(u,v);
            inv.add(v,u);
        }
        dfs(n);
        per(id,dfs_clock,2){
            u = seq[id];
            for(int i = inv.head[u];i;i=inv.G[i].next) 
                if(dfn[inv.G[i].to]) sdo[u] = min(sdo[u],sdo[eval(inv.G[i].to)]);
            ve[seq[sdo[u]]].push_back(u);
            int f = fa[u];ufa[u] = fa[u];
            for(vector<int>::iterator it = ve[f].begin();it != ve[f].end();++it){
                int x = eval(*it);
                ido[*it] = sdo[*it] == sdo[x] ? f : x;
            }ve[f].clear();
        }
        rep(i,2,dfs_clock) u = seq[i],ido[u] = ido[u] == seq[sdo[u]] ? ido[u] : ido[ido[u]];
        rep(i,1,n-1) nwg.add(ido[i],i); // nwg 中储存支配树
    }
    return 0;
}
}}}

struct Graph{
    struct Edge{
        int to,next;
    }G[maxm];
    int head[maxn],cnt;
    void clear(){
        memset(head,0,sizeof head);
        cnt = 0;
    }
    void add(int u,int v){
        G[++cnt].to = v;
        G[cnt].next = head[u];
        head[u] = cnt;
    }
}ori,inv,nwg;
int ufa[maxn],pos[maxn],ido[maxn],sdo[maxn];
int find(int x){
    if(x == ufa[x]) return ufa[x];
    int r = find(ufa[x]);
    if(sdo[pos[ufa[x]]] < sdo[pos[x]]) pos[x] = pos[ufa[x]];
    return (ufa[x] = r);
}
inline int eval(int x){
    find(x);return pos[x];
}
int n,m,dfn[maxn],seq[maxn],dfs_clock;
int fa[maxn];
void dfs(int u){
    dfn[u] = ++ dfs_clock;
    seq[dfs_clock] = u;
    sdo[u] = dfs_clock;
    for(int i = ori.head[u],v;i;i = ori.G[i].next){
        v = ori.G[i].to;
        if(dfn[v]) continue;
        fa[v] = u;
        dfs(v);
    }
}
vector<int>ve[maxn];
int main(){
    while(scanf("%d%d",&n,&m) != EOF){
        rep(i,1,n) ufa[i] = i,pos[i] = i;
        ori.clear();inv.clear();nwg.clear();
        rep(i,1,n) ve[i].clear(),dfn[i] = seq[i] = ido[i] = sdo[i] = sum[i] = fa[i] = 0;
        dfs_clock = 0;
        int u,v;
        rep(i,1,m){
            read(u);read(v);
            ori.add(u,v);
            inv.add(v,u);
        }
        dfs(n);
        per(id,dfs_clock,2){
            u = seq[id];
            for(int i = inv.head[u];i;i=inv.G[i].next) 
                if(dfn[inv.G[i].to]) sdo[u] = min(sdo[u],sdo[eval(inv.G[i].to)]);
            ve[seq[sdo[u]]].push_back(u);
            int f = fa[u];ufa[u] = fa[u];
            for(vector<int>::iterator it = ve[f].begin();it != ve[f].end();++it){
                int x = eval(*it);
                ido[*it] = sdo[*it] == sdo[x] ? f : x;
            }ve[f].clear();
        }
        rep(i,2,dfs_clock) u = seq[i],ido[u] = ido[u] == seq[sdo[u]] ? ido[u] : ido[ido[u]];
        rep(i,1,n-1) nwg.add(ido[i],i); // nwg 中储存支配树
    }
    return 0;
}