当前位置：首页 > news >正文

【图论】基环树

news 2025/8/6 7:47:06

基环树其实并不是树，是指有n个点n条边的图，我们知道n个点n-1条边的连通图是树，再加一条边就会形成一个环，所以基环树中一定有一个环，长下面这样：
在这里插入图片描述
由基环树可以引申出基环内向树和基环外向树

基环内向树如下，特点是每个点的出度为1
在这里插入图片描述
基环外向树如下，特点是每个点的入度为1

下面放点题，做到相关题目随时更新

基环树+组合数学

CF 1454E Number of Simple Paths

先记录环上的点，每个环上的点引出去的子树中，两点之间都只有一条路径，然后子树和其他点之间都有两条路径（因为有个环），可以循环计算每个子树，答案累加即可

#include <bits/stdc++.h>using namespace std;typedef pair<int, int> PII;#define int long longvoid solve()
{int n;cin >> n;vector<vector<int>> g(n + 1);vector<int> in(n + 1);for (int i = 0 ;i < n; i ++ ){int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);in[a] ++ , in[b] ++ ;}queue<int> q;for (int i = 1; i <= n; i ++ ) {if (in[i] == 1) q.push(i);}while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ){int j = g[t][i];in[j] -- ;if (in[j] == 1) q.push(j);}}vector<int> huan;vector<int> st(n + 1);for (int i = 1; i <= n; i ++ ){if (in[i] > 1){huan.push_back(i);st[i] = true;}}int ans = 0, sumtmp, sum = 0;vector<bool> visited(n + 1);function<void(int, int)> dfs = [&](int u, int fa){sumtmp ++ ;if (visited[u]) return;visited[u] = true;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa || visited[j] || st[j]) continue;dfs(j, u);}return;};for (auto i : huan){sumtmp = 0;dfs(i, -1);ans += sumtmp * (sumtmp - 1) / 2;ans += (sumtmp - 1) * (n - sumtmp - sum) * 2;sum += sumtmp - 1;}ans += huan.size() * (huan.size() - 1);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

基环内向树+dfs

牛客寒假集训1K 牛镇公务员考试

基环内向树（准确的说应该是森林）

编号 i 向 a[i] 连边，表示对其限制，我们可以发现环之外的链对答案没什么影响，因为确定了环上一点，可以倒推出链上的所有答案（原因就是约束关系），所以我们在环上任取一点，枚举这个点的五种答案，然后遍历一下环看这个答案是否合法

因为不保证联通，所以需要遍历每一个点

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;
const int maxn = 1e6 + 1;
const int mod = 998244353;void solve()
{int n;cin >> n;vector<int> a(n + 1);vector<string> s(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i] >> s[i];vector<bool> st(n + 1);int ans = 1;for (int i = 1; i <= n; i ++ ){if (st[i]) continue;int j = i;vector<int> huan;for (; !st[j]; j = a[j]){huan.push_back(j);st[j] = true;}auto iter = find(huan.begin(), huan.end(), j);if (iter == huan.end()) continue;huan = {iter, huan.end()};int tmp = 0;for (int k = 0; k < 5; k ++ ){int h = k;for (auto t : huan) h = (int)(s[t][h] - 'A');tmp += h == k;}ans = ans * tmp % mod;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}