AtCoder Beginner Contest 293D

ABC293D

\(N\) 個の頂点を2倍して \(2N\) 個の頂点とみなしたグラフを考える． ひもが結ばれているとき，グラフの方で辺があるとみなす． 各連結成分に対して，サイクルになっているかを判定すれば良い．
実装するときは， 初期で \(a,a'\) が繋がっている事になる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n, m ;

  cin >> n >> m;

  vvll to(2*n);

  UnionFind<ll> uf(n);

  rep(i,m){

    ll a,c;

    char b,d;

    cin >> a >> b >> c >> d;

    --a, --c;

    uf.merge(a,c);

    if(b == 'B') a += n;

    if(d == 'B') c += n;

    to[a].push_back(c);

    to[c].push_back(a);

  }

  rep(i,n){

    to[i].push_back(i+n);

    to[i+n].push_back(i);

  }

  vll vis(2*n);

  auto dfs = [&](auto dfs, ll cu, ll pa = -1) -> bool {

    if(vis[cu]){

      return true;

    }

    vis[cu] = true;

   

    for(auto ne: to[cu]) if(ne != pa){

      if(dfs(dfs, ne, cu)) return true;

    }

   

    return false;

  };

 

  ll x,y;

  x = 0; y = 0;

  for(auto i: uf.representative()){

    if(dfs(dfs, i))  x++;

    else y++;

  }

  cout << x << " "<< y << endl;

  return 0;

}