第九回 アルゴリズム実技検定 G - 連結 ～UF解法～

• https://atcoder.jp/contests/past202112-open/tasks/past202112_g
• AC https://atcoder.jp/contests/past202112-open/submissions/32875853
• N=100なので隣接行列で持つ
• Yes, No判定の時は毎回UF(Union Find)を構築して連結判定する
  • その計算量は？
  • 隣接行列をなめるのにO(N²)
  • 辺があったときにmergeするのにα(N) : アッカーマンの逆関数
    • これは定数と見てよい p14 https://www.slideshare.net/iwiwi/ss-3578491
• 全体の計算量 O( Q N² α(N))

#include <atcoder/dsu>
using namespace atcoder; // 忘れがち

ll mat[100][100];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,Q;
    cin>>N>>Q;

    while(Q--){
      ll ty;cin>>ty;

      if(ty==1){
        // edge
        ll u,v;cin>>u>>v;u--;v--;
        mat[u][v] = 1 - mat[u][v];
        mat[v][u] = 1 - mat[v][u];
      }
      else{
        dsu uf(N);
        rep(i,N){
          FOR(j,i+1,N){
            if(mat[i][j])uf.merge(i,j);
          }
        }
        ll u,v;cin>>u>>v;u--;v--;
        if(uf.same(u,v)){
          p("Yes");
        }else{
          p("No");
        }
      }
    }

    return 0;
}