n度あることはn+1度ある

憶測が多いブログなので鵜呑みにしないこと

ABC075 C - Bridge

初めてUnion-Findを使用してACした問題なのでメモ。
流れとしては
1. i番目に入力された辺を除いたグラフを作る
2. その辺を構成する頂点が接続されているか確かめる
といった感じです。
解説ではDFSを使用しているので、確認用の配列なども必要になりますが、公開されているものを使用することでmain内は簡潔に出来ていると思います。(DFSのほうも構造体やクラスにまとめてしまえば同じようになると思いますが・・・)
dai1741さんが公開しているUnion-Findを使用してACしました。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < int(n); i++)

struct UnionFind{
  vector<int> par;
  vector<int> sizes;
  UnionFind(int n) : par(n), sizes(n, 1) {
    rep(i,n) par[i] = i;
  }
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sizes[x] < sizes[y]) swap(x, y);
    par[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  void print(){
    for(auto x:par)
        cout<<x<<" ";
    cout<<endl;
  }
};
int main(){
    int n,m;
    cin>>n>>m;
    vector<int[2]> sides(m);
    for(int i = 0; i<m; i++)
        cin>>sides[i][0]>>sides[i][1];
    int count=0;
    for(int i = 0; i<m; i++){
        UnionFind un(n);
        for(int j = 0; j<m; j++){
            if(j==i)
                continue;
            un.unite(sides[j][0]-1,sides[j][1]-1);
        }
        if(!un.same(sides[i][0]-1,sides[i][1]-1))
            count++;
    }
    cout<<count;
}