結果

問題 No.317 辺の追加
コンテスト
ユーザー vjudge1
提出日時 2026-02-03 10:45:29
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,504 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 542 ms
コンパイル使用メモリ 56,892 KB
実行使用メモリ 8,156 KB
最終ジャッジ日時 2026-02-03 10:45:32
合計ジャッジ時間 3,440 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

// ?????????????????1e7+10?
const int MAXN = 2e6 + 10;
// ???????????0???memset??????
int parent[MAXN];  // ??????
int sz[MAXN];      // ???????????
bool vis[MAXN];    // ?????????????
// ?????????????????printf??????2e6???+???
char buf[MAXN * 8];
int buf_pos;       // ?????

// ?????????getchar??scanf?3~5????int?
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

// ????????????int???????
inline void write(int x) {
    if (x < 0) { // ??-1???
        buf[buf_pos++] = '-';
        x = -x;
    }
    // ?????????
    int tmp[10], cnt = 0;
    if (x == 0) tmp[cnt++] = 0;
    while (x) {
        tmp[cnt++] = x % 10;
        x /= 10;
    }
    // ???????
    while (cnt--) {
        buf[buf_pos++] = tmp[cnt] + '0';
    }
    buf[buf_pos++] = ' '; // ????????
}

// ??????????????????????
inline int find(int u) {
    // ?????
    int root = u;
    while (parent[root] != root) {
        root = parent[root];
    }
    // ????????????????
    while (parent[u] != root) {
        int tmp = parent[u];
        parent[u] = root;
        u = tmp;
    }
    return root;
}

// ?????????????????????
inline void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    // ????????????????
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
}

int main() {
    // ???????????stdio??????????????
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    buf_pos = 0; // ??????????
    
    // ????N?M
    int N = read();
    int M = read();
    
    // ???????????????????1
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }
    // ??vis?????0???memset??????
    
    // ??M???????+??
    for (int i = 0; i < M; ++i) {
        int u = read();
        int v = read();
        unite(u, v);
    }
    
    // ??????????k
    int k = 0;
    for (int i = 1; i <= N; ++i) {
        int root = find(i);
        if (!vis[root]) {
            k++;
            vis[root] = true;
        }
    }
    
    // ??1~N????????????????????IO?
    for (int i = 1; i <= N; ++i) {
        if (i > k) write(-1);
        else write(k - i);
    }
    
    // ???????????????????
    printf("%s\n", buf);
    
    return 0;
}
0