找环板子

佚名 7年前 (2019-04-22) 随笔 1614人围观抢沙发百度已收录

只含简单环的图可以找出所有环.

void get(int x, int y) {
    if (dep[x]<dep[y]) return;
    ++cnt;
    v[cnt].pb(x);
    for (; x!=y; x=fa[x]) v[cnt].pb(x);
}
void dfs(int x, int f) {
    fa[x]=f,dep[x]=dep[f]+1;
    for (int y:g[x]) if (y!=f) {
        if (dep[y]) get(x,y);
        else dfs(y,x);
    }   
}

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。