鉄道同好会 [yukicoder No.583]

https://yukicoder.me/problems/no/583

前提知識

• オイラー路
• UnionFind

解法

https://yukicoder.me/submissions/212283

今回の問題は言い換えると、与えられた無向グラフのオイラー路が存在するかを判定するプログラムになる。
全ての辺を使うオイラー路の存在条件は

• 辺でつながれている全ての頂点が連結である(UnionFindでやる)
• 次数が奇数の頂点が0個か2個

int N, M;
vector<int> E[505];
int vis[505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    UnionFind uf(N);

    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
        uf(a, b);
        vis[a] = vis[b] = 1;
    }

    map<int, int> cnt;
    rep(i, 0, N) cnt[E[i].size() % 2]++;

    int ok = 1;
    int c = 0;
    rep(i, 0, N) if (vis[i]) c = i;
    rep(i, 0, N) if (vis[i] and uf[c] != uf[i]) ok = 0;

    if (ok and (cnt[1] == 0 or cnt[1] == 2)) printf("YES\n");
    else printf("NO\n");   
}