結果

問題 No.2202 贅沢てりたまチキン
コンテスト
ユーザー zezero
提出日時 2023-02-03 21:53:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,454 bytes
コンパイル時間 748 ms
コンパイル使用メモリ 93,664 KB
最終ジャッジ日時 2025-02-10 09:09:10
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

class union_find {
public:
vector<int> par,rank,lsize;
union_find(int n): par(n),rank(n),lsize(n){
   for (int i=0;i < n;i++){
      par[i]=i;
      rank[i]=0;
      lsize[i]=1;
   }
}

int find(int x){
   if (par[x]==x){
      return x;
   }
   else{
      return par[x] = find(par[x]); 
   }
}

void unite(int x ,int y){
   x=find(x);
   y=find(y);
   if (x==y) return;
   if (rank[x] < rank[y]){
      lsize[y] += lsize[x];
      lsize[x] = -1;
      par[x] = y;
   }else{
      lsize[x] += lsize[y];
      lsize[y] = -1;
      par[y]=x;
      if (rank[x]==rank[y]) rank[x]++;
   }   
}

bool same(int x, int y){
   return find(x) == find(y);
}

int size(int x){
   if (lsize[x] == -1){
      x=find(x);
   }
   return lsize[x];
}

int groups(){
   int res = 0;
   for (int i = 0;i < par.size();i++){
      if (i == par[i]) res++;
   }
   return res;
}

};

void solve(){
  int n,m;
  cin >> n >> m;
  union_find d(2*n);
  for (int i = 0; i < m;i++){
    int a,b;
    cin >> a >> b;
    a--;b--;
    d.unite(a,b+n);
    d.unite(a+n,b);
  }
  if (d.groups() == 1){
    cout << "Yes\n";
  }
  else cout << "No\n";

  return;
}

  

int main(){
  int tt = 1;
  //cin >> tt;
  while(tt--){
	  solve();
  }
  return 0;
}
0