概念

基环树指$n$个点$n$条边的连通图, 仅比树多一条边, 有大部分树的性质.

重要的事 找环

tarjan找环, 给一份容易实现的代码（不能找重边和自环）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int n, m;
vector<int> G[MAXN];
namespace Circle {
    vector<int> circle; // 环上的点
    int tag[MAXN]; // 标记: -1未访问; 1访问过; 2在环上
    void init() {
        for(int i = 0; i < n; i ++) {
            tag[i] = -1;
        }
    }
    int dfs(int u, int f) {
        if(tag[u] != -1) {
            return u;
        }
        tag[u] = 1;
        for(auto v : G[u]) if(v != f) {
            int t = dfs(v, u);
            if(t > -1) {
                circle.push_back(u);
                tag[u] = 2;
                return t == u ? -1 : t;
            }
        }
        return -1;
    }
}

例题

旅行

  • 题目大意: 给定一棵普通树或者基环树, 求访问全部节点最小的字典序(每个节点只记录第一次访问).

  • 对于一般树, 可以$1$节点开始跑; 对于基环树, 可以删一条边使其变成普通树, 时间复杂度$O(n^2)$

  • 参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e9 + 7, MAXN = 5e3 + 10, mod = 998244353;
int n, m;
vector<int> G[MAXN];
vector<int> res, ste;
namespace Circle {
    vector<int> circle;
    int tag[MAXN];
    void init() {
        for(int i = 0; i < n; i ++) {
            tag[i] = -1;
        }
    }
    int dfs(int u, int f) {
        if(tag[u] != -1) {
            return u;
        }
        tag[u] = 1;
        for(auto v : G[u]) if(v != f) {
            int t = dfs(v, u);
            if(t > -1) {
                circle.push_back(u);
                tag[u] = 2;
                return t == u ? -1 : t;
            }
        }
        return -1;
    }
}
bool cmp(vector<int> &a, vector<int> &b) {
    if(!a.size()) {
        return 1;
    } else {
        for(int i = 0; i < n; i ++) {
            if(a[i] != b[i]) {
                return a[i] > b[i];
            }
        }
    }
    return 0;
}
int du = -1, dv = -1; // 删的边
void dfs(int u, int p) {
    ste.push_back(u);
    for(int v : G[u]) if(v != p) {
        if((du == u && dv == v) || du == v && dv == u) continue;
        dfs(v, u);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        u --, v --;
        G[u].push_back(v), G[v].push_back(u);
    }
    for(int i = 0; i < n; i ++) {
        sort(G[i].begin(), G[i].end());
    }
    if(m == n - 1) {
        dfs(0, 0);
        res = ste;
    } else {
        Circle::init();
        Circle::dfs(0, 0);
        for(int i = 0; i < Circle::circle.size() - 1; i ++) {
            du = Circle::circle[i], dv = Circle::circle[i + 1];
            ste.clear();
            dfs(0, 0);
            if(cmp(res, ste)) {
                res = ste;
            }
        }
    }
    for(int i : res) {
        cout << i + 1 << ' ';
    }
}