제출 #1340469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1340469		kawhiet	Ronald (COCI17_ronald)	C++20	120 / 120	20 ms	448 KiB

ronald

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

struct DSU {
    vector<int> p, cnt, sz;

    DSU(int n) {
        cnt.resize(n);
        sz.assign(n, 1);
        p.assign(n, -1);
    }

    int root(int x) { return (p[x] == -1 ? x : (p[x] = root(p[x]))); }

    bool link(int x, int y) {
        x = root(x); y = root(y);
        cnt[x]++;
        if (x == y) return false;
        p[y] = x;
        sz[x] += sz[y];
        cnt[x] += cnt[y];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    int groups = n;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        if (dsu.link(x, y)) {
            groups--;
        }
    }
    if (groups > 2) {
        cout << "NE\n";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        if (dsu.root(i) == i) {
            int k = dsu.sz[i];
            if (dsu.cnt[i] != k * (k - 1) / 2) {
                cout << "NE\n";
                return 0;
            }
        }
    }
    cout << "DA\n";
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15
• Subtask 7: 15 / 15
• Subtask 8: 15 / 15