Guest User

Untitled

a guest
Apr 25th, 2019
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. using std::vector;using std::endl;
  6. using std::cin;using std::cout;
  7. using std::fill;using std::pair;
  8.  
  9. pair<int,int> fp(int a,vector<pair<int,int> >&par){
  10.     if(a!=par[a].first){
  11.         int parity=par[a].second;
  12.         par[a] = fp(par[a].first,par);
  13.         par[a].second^=parity;
  14.     }
  15.     return par[a];
  16. }
  17.  
  18. bool merge(int a,int b,vector<pair<int,int> >&par,vector<int>& rank){
  19.     pair<int,int> pa=fp(a,par) , pb=fp(b,par);
  20.    // cout<<par[a].first<<" "<<par[a].second<<" "<<par[b].first<<" "<<par[b].second<<endl;
  21.     if(pa.first==pb.first){
  22.         if(pa.second==pb.second) return false;
  23.     }
  24.     else{
  25.         if(rank[pa.first]<rank[pb.second])
  26.         std::swap(pa,pb);
  27.             par[pb.first].first=pa.first;
  28.             par[pb.first].second=pa.second^pb.second^1;
  29.         if(rank[pa.first]==rank[pb.second]) rank[pa.first]++;
  30.     }
  31.     return true;
  32. }
  33.  
  34. int main() {
  35.     std::ios::sync_with_stdio(false);
  36.     cin.tie(0);
  37.     bool flag;
  38.     int t,i,n,p,q,j;
  39.     long c;
  40.     cin>>t;
  41.     vector<pair<int,int> >par;
  42.     vector<int>rank;
  43.     for(i=0;i<t;i++){
  44.         cin>>n>>c;
  45.         par.resize(n+1);
  46.         rank.resize(n+1);
  47.         flag=true;
  48.         for(j=0;j<=n;j++) par[j].first=j,par[j].second=0,rank[j]=0;
  49.         for(j=0;j<c && flag;j++){
  50.             cin>>p>>q;
  51.             flag=merge(p,q,par,rank);
  52.         }
  53.         cout<<"Scenario #"<<i+1<<":\n";
  54.         if(!flag) cout<<"Suspicious bugs found!\n";
  55.         else cout<<"No suspicious bugs found!\n";
  56.          //for(j=1;j<=n;j++) cout<<par[j].first<<" "<<par[j].second<<endl;
  57.         par.clear();
  58.         rank.clear();
  59.     }
  60. }
Add Comment
Please, Sign In to add comment