最喜爱的颜色(Favorite Colors G) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    vector<int> p(n + 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) {
        while (p[x] != x) x = p[x] = p[p[x]];
        return x;
    };
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (adj[i].size() > 1) q.push(i);
    }
    while (!q.empty()) {
        int u = find(q.front());
        q.pop();
        while (adj[u].size() > 1) {
            int v1 = find(adj[u].back());
            adj[u].pop_back();
            int v2 = find(adj[u].back());
            if (v1 == v2) continue;
            if (adj[v1].size() < adj[v2].size()) swap(v1, v2);
            p[v2] = v1;
            for (int w : adj[v2]) adj[v1].push_back(w);
            adj[v2].clear();
            if (adj[v1].size() > 1) q.push(v1);
        }
    }
    vector<int> col(n + 1, 0);
    int curCol = 0;
    for (int i = 1; i <= n; ++i) {
        int r = find(i);
        if (!col[r]) col[r] = ++curCol;
        cout << col[r] << "\n";
    }
    return 0;
}