子任务1

参考代码

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

const int N = 2e5 + 10;
int a[N], b[N];
int n, k, m;

set<int> pos[N];
int A[N];

int main() {
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= n; i++) A[i] = i;
    for (int i = 1; i <= n; i++) pos[i].insert(i);

    m = (m - 1) % (n * k) + 1;

    for (int i = 0; i < m; i++) {
        pos[A[a[i % k]]].insert(b[i % k]);
        pos[A[b[i % k]]].insert(a[i % k]);
        swap(A[a[i % k]], A[b[i % k]]);
    }

    for (int i = 1; i <= n; i++) cout << pos[i].size() << '\n';
}

子任务2

参考代码

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

const int N = 2e5 + 10;
int a[N], b[N];
int n, k;
long long m;

set<int> pos[N];
int A[N];

bool v[N];
int ans[N];

int main() {
    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= n; i++) A[i] = i;
    for (int i = 1; i <= n; i++) pos[i].insert(i);


    for (int i = 0; i < k; i++) {
        pos[A[a[i]]].insert(b[i]);
        pos[A[b[i]]].insert(a[i]);
        swap(A[a[i]], A[b[i]]);
    }
    for (int i = 1; i <= n; i++) {
        if (v[i]) continue;
        set<int> s;
        int j = i;
        while (!v[j]) {
            s.insert(pos[j].begin(), pos[j].end());
            v[j] = true;
            j = A[j];
        }
        j = i;
        do {
            ans[j] = s.size();
            j = A[j];
        } while (j != i);
    }


    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}