ARC037 B:バウムテスト

競技プログラミング

またまたまたグラフ問題。
半日かけた割に完全に理解しているとは言い難い。

https://atcoder.jp/contests/arc037/tasks/arc037_b

最初はdfsで解こうとしたが、案の定バグりまくる。公式解説を見ても理解できない。

そこで方針を変えることにした。互いに素な集合が与えられる可能性があるなら、UnionFindが使えるんじゃないか？

だがUnionFindだと連結グラフが閉路を持つかどうかがわからない。併合の際に辺を付け替えてしまうからだ。

蟻本を見たところ、辺の数がグラフの頂点数 - 1 と等しいなら、それは木であると判定できるらしい。辺の数を管理する変数を追加すれば解けそうか？

まあここまでやっといて結局自力（？）ACできなかったわけだが。他の人の回答をがっつりパクりつつひいひい言いながら書き上げたのが以下のコード。

class UnionFindTree {
  private:
    vector<int> m_parent; // 親ノードの番号を格納。-1なら自分自身が親(root)

  public:
    // 頂点数で初期化。最初は全てのノードが非連結。
    UnionFindTree(int x) : m_parent(x, -1) {}

    // xがどのグループに属しているかを調べる。
    int root(int x) {
        if (m_parent[x] < 0) {
            return x;
        }
        m_parent[x] = root(m_parent[x]); // 高速化のため、親を根に繋ぎかておく。
        return m_parent[x];
    }

    // xの属するグループの頂点数を調べる。
    int size(int x) { return -m_parent[root(x)]; }

    // xが属する集合とyが属する集合を連結する。
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) {
            return false; // すでにくっついているからくっつけない。
        }

        // ノード番号の大きい方(x)に小さい方(y)をくっつけたい。
        if (size(x) < size(y))
            swap(x, y);

        // xのサイズを更新。
        m_parent[x] += m_parent[y];
        // yの親をxにする。
        m_parent[y] = x;
        return true;
    }

    // 同じグループか？
    bool is_same_group(int x, int y) { return root(x) == root(y); }
};

signed main() {
    int n, m;
    cin >> n >> m;
    UnionFindTree uf(n);
    vector<int> nodes(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        uf.unite(a, b);
        nodes[i] = a;
    }

    // 各集合における辺数。根以外のインデックスには0が格納される。
    vector<int> edges(n, 0);
    for (int i = 0; i < m; i++) {
        edges[uf.root(nodes[i])] += 1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        // グラフの木判定：頂点数 - 1 == 辺数
        if (uf.size(i) - 1 == edges[i]) {
            ans++;
        }
    }
    cout << ans << endl;
}