結果

問題 No.1640 簡単な色塗り
ユーザー 👑 ygussany
提出日時 2021-08-06 23:57:07
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 1,632 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2024-06-29 16:27:35
合計ジャッジ時間 9,410 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
typedef struct List {
    struct List *next;
    int v, id;
} list;
int main()
{
    int i, N, M, u, w, deg[500001] = {};
    list *adj[500001] = {}, e[1000001], *p;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d %d", &u, &w);
        e[i*2].v = w;
        e[i*2+1].v = u;
        e[i*2].id = i + 1;
        e[i*2+1].id = i + 1;
        e[i*2].next = adj[u];
        e[i*2+1].next = adj[w];
        adj[u] = &(e[i*2]);
        adj[w] = &(e[i*2+1]);
        deg[u]++;
        deg[w]++;
    }
    for (u = 1; u <= N; u++) if (deg[u] == 0) break;
    if (u <= N) {
        printf("No\n");
        fflush(stdout);
        return 0;
    }
    
    int x, ans[500001] = {}, q[500001], head, tail = 0;
    for (u = 1; u <= N; u++) if (deg[u] == 1) q[tail++] = u;
    for (head = 0; head < tail; head++) {
        u = q[head];
        for (p = adj[u]; p != NULL; p = p->next) {
            w = p->v;
            i = p->id;
            if (ans[i] == 0) {
                ans[i] = u;
                deg[w]--;
                if (deg[w] == 1) q[tail++] = w;
                break;
            }
        }
        if (p == NULL) {
            printf("No\n");
            fflush(stdout);
            return 0;
        }
    }
    if (tail < N) {
        for (x = 1; x <= N; x++) {
            if (deg[x] <= 1) continue;
            for (p = adj[x]; p != NULL; p = p->next) {
                u = p->v;
                i = p->id;
                if (ans[i] == 0) {
                    ans[i] = x;
                    deg[u]--;
                    break;
                }
            }
            for (; u != x; u = w) {
                for (p = adj[u]; p != NULL; p = p->next) {
                    w = p->v;
                    i = p->id;
                    if (ans[i] == 0) {
                        ans[i] = u;
                        deg[w]--;
                        break;
                    }
                }
                if (p == NULL) break;
            }
        }
    }
    for (i = 1; i <= N; i++) if (ans[i] == 0) break;
    if (i <= N) printf("No\n");
    else {
        printf("Yes\n");
        for (i = 1; i <= N; i++) printf("%d\n", ans[i]);
    }
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0