基环树 找环

dfs + stack

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int N = 1010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int d[N];
bool stk[N];
vector<int> cirs;
stack<int> path;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs_cir(int u, int p){
    if(stk[u]){
        while (path.top() != u){
            cirs.push_back(path.top());
            path.pop();
        }
        cirs.push_back(u);
        return true;
    }
    if(st[u]) return false;

    st[u] = true;
    path.push(u);
    stk[u] = true;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == p) continue;
        if(dfs_cir(j, u)) return true;
    }
    path.pop();
    stk[u] = false;

    return false;
}

void dfs_dep(int u, int depth){
    st[u] = true;
    d[u] = depth;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!st[j])
            dfs_dep(j, depth + 1);
    }
}

int main(){
    int T; cin >> T;
    for(int C = 1;C <= T;C ++ ){
        cin >> n;
        memset(h, -1, sizeof h);
        idx = 0;
        memset(st, false, sizeof st);
        memset(stk, false, sizeof stk);
        cirs.clear();
        path = stack<int>();

        for(int i = 0;i < n;i ++ ){
            int a, b; cin >> a >> b;
            add(a, b), add(b, a);
        }

        dfs_cir(1, -1);

        memset(st, 0, sizeof st);
        for (auto c : cirs) st[c] = true;
        for (auto c : cirs) dfs_dep(c, 0);

        printf("Case #%d:", C);
        for (int i = 1; i <= n; i ++) printf(" %d", d[i]);
        puts("");
    }
    return 0;
}

dfs + timestamp

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int N = 1010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
int fa[N];
int d[N];
bool st[N];
vector<int> cirs;
int dfn[N], timestamp;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs_cir(int u, int p){
    dfn[u] = ++ timestamp;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(j == p) continue;
        if(dfn[j]){
            if(dfn[j] < dfn[u]) continue;
            for(;j != u;j = fa[j]) cirs.push_back(j);
            cirs.push_back(u);
        }else fa[j] = u, dfs_cir(j, u);
    }
}

void dfs_dep(int u, int depth){
    st[u] = true;
    d[u] = depth;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!st[j])
            dfs_dep(j, depth + 1);
    }
}

int main(){
    int T; cin >> T;
    for(int C = 1;C <= T;C ++ ){
        cin >> n;
        memset(h, -1, sizeof h);
        idx = 0;
        cirs.clear();
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        timestamp = 0;

        for(int i = 0;i < n;i ++ ){
            int a, b; cin >> a >> b;
            add(a, b), add(b, a);
        }

        dfs_cir(1, -1);

        memset(st, 0, sizeof st);
        for (auto c : cirs) st[c] = true;
        for (auto c : cirs) dfs_dep(c, 0);

        printf("Case #%d:", C);
        for (int i = 1; i <= n; i ++) printf(" %d", d[i]);
        puts("");
    }
    return 0;
}

dfs + 并查集

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

const int N = 1010, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
bool st[N];
int d[N];
vector<int> cirs;
vector<int> path;
int St, Ed;
int p[N];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; 
}

void dfs_cir(int u){
    path.push_back(u);
    st[u] = true;
    if(u == Ed){
        for(auto t : path) cirs.push_back(t);
        return ;
    }
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(st[j]) continue;
        dfs_cir(j);
    }

    path.pop_back();
}
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void dfs_dep(int u, int depth){
    st[u] = true;
    d[u] = depth;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!st[j])
            dfs_dep(j, depth + 1);
    }
}

int main(){
    int T; cin >> T;
    for(int C = 1;C <= T;C ++ ){
        cin >> n;
        memset(h, -1, sizeof h);
        idx = 0;
        for(int i = 1;i <= n;i ++ ) p[i] = i;
        memset(st, 0, sizeof st);
        cirs.clear();
        path.clear();

        for(int i = 0;i < n;i ++ ){
            int a, b; cin >> a >> b;
            int pa = find(a), pb = find(b);
            if(pa == pb){
                St = a, Ed = b;
            }else{
                p[pa] = pb;
                add(a, b);
                add(b, a);
            }
        }

        dfs_cir(St);

        memset(st, 0, sizeof st);
        for (auto c : cirs) st[c] = true;
        for (auto c : cirs) dfs_dep(c, 0);

        printf("Case #%d:", C);
        for (int i = 1; i <= n; i ++) printf(" %d", d[i]);
        puts("");
    }
}

topsort

（如果是有向图 还可以用tarjan）