构造，CF 2029D - Cool Graph

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

我们对每条 <u, v>，u != 1 && v != 1 的边<u, v> 做 <1, u, v> 的操作后会得到什么？

一个棵以1为根且所有父节点都是1的树，以及一些孤立点

我们任意找到 根节点1 的一个儿子，遍历所有剩下的孤立点 y 做如下操作：

<1, x, y>

x = y

最后一定能构造出一棵树

总操作次数：O(n + m)，没有超过题目上限，且时间复杂度优于官解

2、复杂度

时间复杂度： O(N + M)空间复杂度：O(N + M)

3、代码详解

 ​

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::tuple<int, int, int>> ans;
    std::vector<int> f(n);

    for (int i = 0; i < m; ++ i) {
        int u, v;
        std::cin >> u >> v;
        -- u, -- v;
        if (u == 0 || v == 0) {
            f[u == 0 ? v : u] ^= 1;
        } else {
            ans.emplace_back(1, u + 1, v + 1);
            f[u] ^= 1;
            f[v] ^= 1;
        }
    }

    if (std::ranges::max(f) > 0) {
        int x = std::find(f.begin(), f.end(), 1) - f.begin();

        for (int i = 1; i < n; ++ i) {
            if (f[i] == 0) {
                ans.emplace_back(1, x + 1, i + 1);
                x = i;
            }
        }
    }

    std::cout << ans.size() << '\n';
    for (auto &[a, b, c] : ans) {
        std::cout << a << ' ' << b << ' ' << c << '\n';
    }
}

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

#ifdef DEBUG
    int START = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    std::cin >> t;

    while (t --) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - START << '\n';
#endif
    return 0;
}