D - Unicyclic Components

atcoder.jp

UnionFindだろうと思ったが、ACLの使い方の理解が浅かったので、BFSで解いてしまった。

void solve(long long N, long long M, std::vector<long long> u, std::vector<long long> v){
    vvl G(N+9);
    REP(i, M) {
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(v[i]);
    }
 
    vb done(N+9);
    FOR(i, 1, N) {
        if (done[i]) continue;
 
        ll ncnt = 0;
        ll bcnt = 0;
        queue<ll> que;
        que.push(i);
        while (!que.empty()) {
            ll cur = que.front();
            que.pop();
            done[cur] = true;
            ncnt++;
 
            bcnt += G[cur].size();
            REP(j, G[cur].size()) {
                ll nxt = G[cur][j];
                if (done[nxt]) continue;
                que.push(nxt);
            }
        }
 
        if (ncnt*2!=bcnt) {
            cout << NO << endl;
            return;
        }
    }
 
    cout << YES << endl;
}

解説によると、dsuではleaderを使えばよかったようだ。

各頂点のleaderでカウント(vs[du.leader(i)]++)して、各連結成分の頂点数を数える。 連結情報の頂点のleaderでカウント(es[D.leader(u[i])]++)して、各連結成分の辺数を数える。

vs==esであればYes、そうでなければNo。