Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <utility>
- using std::vector;using std::endl;
- using std::cin;using std::cout;
- using std::fill;using std::pair;
- pair<int,int> fp(int a,vector<pair<int,int> >&par){
- if(a!=par[a].first){
- int parity=par[a].second;
- par[a] = fp(par[a].first,par);
- par[a].second^=parity;
- }
- return par[a];
- }
- bool merge(int a,int b,vector<pair<int,int> >&par,vector<int>& rank){
- pair<int,int> pa=fp(a,par) , pb=fp(b,par);
- // cout<<par[a].first<<" "<<par[a].second<<" "<<par[b].first<<" "<<par[b].second<<endl;
- if(pa.first==pb.first){
- if(pa.second==pb.second) return false;
- }
- else{
- if(rank[pa.first]<rank[pb.second])
- std::swap(pa,pb);
- par[pb.first].first=pa.first;
- par[pb.first].second=pa.second^pb.second^1;
- if(rank[pa.first]==rank[pb.second]) rank[pa.first]++;
- }
- return true;
- }
- int main() {
- std::ios::sync_with_stdio(false);
- cin.tie(0);
- bool flag;
- int t,i,n,p,q,j;
- long c;
- cin>>t;
- vector<pair<int,int> >par;
- vector<int>rank;
- for(i=0;i<t;i++){
- cin>>n>>c;
- par.resize(n+1);
- rank.resize(n+1);
- flag=true;
- for(j=0;j<=n;j++) par[j].first=j,par[j].second=0,rank[j]=0;
- for(j=0;j<c && flag;j++){
- cin>>p>>q;
- flag=merge(p,q,par,rank);
- }
- cout<<"Scenario #"<<i+1<<":\n";
- if(!flag) cout<<"Suspicious bugs found!\n";
- else cout<<"No suspicious bugs found!\n";
- //for(j=1;j<=n;j++) cout<<par[j].first<<" "<<par[j].second<<endl;
- par.clear();
- rank.clear();
- }
- }
Add Comment
Please, Sign In to add comment