环套树 or 基环树找环

最近学了一个蛮好的bfs找基环树上环的算法；

不过我做起题目来，感觉身心收到了摧残，感觉一题回到语法篇；

废话不多说，介绍找环的方法，以无向基环树为例；

三步求环大法；

第一步在加边的时候，统计一下每个点的度；

第二步用bfs遍历度等于1的点（就是叶子节点，只有一条边）去掉相关的边，并且更新度

第三步从一个度不等于零的点开始进行边遍历；

献上我丑陋的代码

#include<cstdio>
#include<queue>
#include<map>
#include<cstring>
#include<cstdlib>
#include<deque>
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#define inf 0x3f3f3f3f
#define ll long long 
#define M 1010000
using namespace std;
int n , head[M] , net[M << 1] , u[M << 1] , v[M << 1] , d[M] , cnt = 1;
int q[M] , f[M] , du[M] , tot;
ll g[M];
void add(int x , int y , int z){
    u[++cnt] = y , d[cnt] = z , net[cnt] = head[x] , head[x] = cnt;
    ++du[y];
}
void bfs(int x){
    int y , l , r , now;
    l = r = 1; q[1] = x ;
    while (l <= r){
        now = q[l] , ++l , --du[now];
        for (int i = head[now] ; i ; i = net[i]){
            if (du[y = u[i]] > 1){
                if (--du[y] == 1) q[++r] = y;
            }
        }
    }
}
void find_hoop(int x){
    int l , r  , now , y;
    l = r = 1 , q[1] = x; 
    f[++tot] = x ;
    while (l <= r){
        now = q[l] , ++l;
        for (int i = head[now] ; i ; i = net[i]){
            if (du[y = u[i]] && !v[i]){
                v[i] = v[i^1] = 1;
                f[++tot] = y;
                g[tot] = g[tot - 1] + d[i];
                q[++r] = y;
                break; // 一定要break ， 不然会走两条边； 
            }
        }
    }
}
int main(){
//    freopen("A.out" , "w" , stdout);
    freopen("c1.in" , "r" , stdin);
    scanf("%d" , &n);
    for (int i = 1 ; i <= n ; ++i){
        int a , b , c;
        scanf("%d%d%d" , &a , &b , &c);
        add(a , b , c) , add(b , a , c);
    }
    for (int i = 1 ; i <= n ; ++i){
        if (du[i] == 1) bfs(i);
    }
    for (int i = 1 ; i <= n ; ++i){
        if (du[i]){
            find_hoop(i);
            for (int j = 1 ; j <= tot ; ++j){
                du[f[j]] = 0;
            }
        }
    }
    for (int i = 1 ; i <= tot ; ++i){
        printf ("%d " , f[i]);
    }
    printf ("
%lld" , g[tot]);
    return 0;
}

里面说明一个东西， add有向边的时候，我是cnt = 1 开始的；

这样访问一条边的时候，设这条边是i 那么 i^1 , 就是他的反向边，得到另一个点；

f数组记录点， g 记录边权总和（环上的）

有向边的做法也是类似的；

环套树 or 基环树 找环

环套树 or 基环树找环