题解：P11829 [TOIP2024] 栖息地分配

水星湖 · 2025-03-02 10:59:23 · 题解

必然有解。

当图中有 \ge 2 个连通块时，将较小的连通块内所有点放在第一类，剩下大的连通块大小必然 \ge 2，任取一个点作为第二类，剩下的作为第三类，显然合法。

否则，当图中仅有一个连通块时，由于 m\le 2n-4，则求生成树的过程中至多有 n-3 条返祖边，每一条返祖边用并查集合并端点，最后必然剩下 \ge 3 个未合并的集合（n 个点至多合并 n-3 次），直接输出就好了。

#include <bits/stdc++.h>
using namespace std;

namespace z {

#define int long long
const int N = 5e5 + 5;
int fa[N], flag[N], vis[N];
vector<int> p[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { x = find(x), y = find(y); if(x != y) fa[x] = y; }
void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i, flag[i] = 0, vis[i] = 0, p[i].clear(); }
void dfs(int u, int fa) {
    vis[u] = 1;
    for(auto v : p[u]) {
        if(v == fa) continue;
        if(vis[v]) merge(v, u);
        else dfs(v, u);
    }
}
void solve() {
    int n, m; cin >> n >> m;
    init(n);
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        p[u].push_back(v);
        p[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 2; i <= n; i++) if(!vis[i]) {
        vector<int> a1, a2;
        for(int j = 1; j <= n; j++) {
            if(vis[j]) a1.push_back(j);
            else a2.push_back(j);
        }
        if(a1.size() == 1) {
            cout << 1 << " " << a1[0] << '\n';
            cout << 1 << " " << a2[0] << '\n';
            cout << a2.size() - 1 << " ";
            for(auto j : a2) if(j != a2[0]) cout << j << ' ';
            cout << '\n';
        } else if(a2.size() == 1) {
            cout << 1 << " " << a1[0] << '\n';
            cout << 1 << " " << a2[0] << '\n';
            cout << a1.size() - 1 << " ";
            for(auto j : a1) if(j != a1[0]) cout << j << ' ';
        } else {
            cout << a1.size() << " ";
            for(auto j : a1) cout << j << ' ';
            cout << '\n';
            cout << 1 << " " << a2[0] << '\n';
            cout << a2.size() - 1 << " ";
            for(auto j : a2) if(j != a2[0]) cout << j << ' ';
        }
        return;
    }
    vector<int> ans;
    for(int i = 1; i <= n; i++) 
        if(find(i) == i) ans.push_back(i);
    vector<int> a[3];
    for(int i = 0; i <= 2; i++)
        for(int j = 1; j <= n; j++)
            if(find(j) == ans[i])
                a[i].push_back(j), flag[j] = 1;
    for(int i = 1; i <= n; i++) 
        if(!flag[i]) a[0].push_back(i);
    for(int i = 0; i <= 2; i++) {
        cout << a[i].size() << ' ';
        for(auto j : a[i]) cout << j << ' ';
        cout << '\n';
    }
}
void main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int T; cin >> T;
    while(T--) solve();

}

#undef int

}

int main()
{
    z::main();
    return 0;
}