题解归档 - cf406C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf406C
• 本地来源：problems/cf406C/idea.md
• 题目链接：https://codeforces.com/contest/406/problem/C
• 原始标题：cf406C - Graph Cutting

思路

cf406C - Graph Cutting

Each length-2 path is two edges sharing a middle vertex. Therefore we can assign every edge to one of its endpoints as its path center; at every vertex, assigned incident edges must come in pairs.

Equivalently orient every edge toward its chosen center and require every vertex to have even indegree. If m is odd this is impossible. If m is even and the graph is connected, it is possible: orient non-tree back edges arbitrarily to ancestors; process DFS tree bottom-up and orient the parent edge into the child iff the child's current indegree parity is odd, otherwise orient it into the parent.

After all indegrees are even, pair incoming neighbors at each vertex and output (u, v, w).

代码

来源：problems/cf406C/solution.cpp

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

const int N = 100005;

int n, m;
vector<pair<int,int>> g[N];
int vis[N], dep[N], fa[N], fe[N], pd[N];
vector<int> in[N];

void dfs(int x) {
    vis[x] = 1;
    for (auto [y, id] : g[x]) {
        if (id == fe[x]) continue;
        if (!vis[y]) {
            fa[y] = x;
            fe[y] = id;
            dep[y] = dep[x] + 1;
            dfs(y);
        } else if (dep[y] < dep[x]) {
            in[y].push_back(x);
            pd[y] ^= 1;
        }
    }
    if (x != 1) {
        if (pd[x]) {
            in[x].push_back(fa[x]);
            pd[x] ^= 1;
        } else {
            in[fa[x]].push_back(x);
            pd[fa[x]] ^= 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    if (m & 1) {
        cout << "No solution\n";
        return 0;
    }

    dfs(1);
    if (pd[1]) {
        cout << "No solution\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (int)in[i].size(); j += 2) {
            cout << in[i][j] << ' ' << i << ' ' << in[i][j + 1] << '\n';
        }
    }
    return 0;
}