fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int N,Q,flag,sizee,a,b,t,type,ans=1;
  4.  
  5. struct node
  6. {
  7. 	int height;
  8. 	struct node *parent;
  9. 	int data;
  10. }*repa,*repb;
  11.  
  12. map<int,struct node *> maap;
  13. vector<pair<int,int> > v;
  14. vector<int> adj[100005];
  15. int level[100005];
  16. bool visited[100005];
  17.  
  18. void makeset(int data)
  19. {
  20.     struct node *p=new node;
  21.     p->height=0;
  22.     p->parent=p;
  23.     p->data=data;
  24.     maap[data]=p;
  25. }
  26.  
  27. struct node* findrep(struct node *p)
  28. {
  29. 		struct node* parent=p->parent;
  30.  
  31. 		if(parent==parent->parent)
  32. 		{
  33. 			return parent;
  34. 		}
  35.  
  36. 		struct node *result=findrep(parent);
  37. 		p->parent=result;
  38. 		return result;
  39. }
  40.  
  41. void joinset(int a,int b)
  42. {
  43. 	struct node *node1=maap[a];
  44. 	struct node *node2=maap[b];
  45.  
  46. 	struct node *rep1=findrep(node1);
  47. 	struct node *rep2=findrep(node2);
  48.  
  49. 	if(rep1==rep2)
  50. 	return;
  51.  
  52. 	if(rep1->height>=rep2->height)
  53. 	{
  54. 		rep2->parent=rep1;
  55. 		if(rep1->height==rep2->height)
  56. 		rep1->height+=1;
  57. 	}
  58. 	else
  59. 		rep1->parent=rep2;
  60. }
  61.  
  62.  
  63. bool isbipartite(int src)
  64. {
  65.     int sizee,i;
  66.     queue<pair<int,int> > q;
  67.  
  68.     q.push(make_pair(src,0));
  69.     visited[src]=true;
  70.     pair<int,int> p;
  71.     while(q.size())
  72.     {
  73.         p=q.front();
  74.         q.pop();
  75.         sizee=adj[p.first].size();
  76.         level[p.first]=p.second;
  77.  
  78.         for(i=0;i<sizee;i++)
  79.         {
  80.             if(!visited[adj[p.first][i]])
  81.             {
  82.                 visited[adj[p.first][i]]=true;
  83.                 q.push(make_pair(adj[p.first][i],p.second+1));
  84.             }
  85.             else
  86.             {
  87.                 if(p.second==level[adj[p.first][i]])
  88.                 return false;
  89.             }
  90.         }
  91.  
  92.     }
  93.     return true;
  94. }
  95.  
  96. int main()
  97. {
  98.     int i;
  99.    cin>>t;
  100.    while(t--)
  101.    {
  102.     cin>>N>>Q;
  103.     flag=1;
  104.     maap.clear();
  105.     memset(visited,false,sizeof(visited));
  106.     v.clear();
  107.  
  108.     adj[0].clear();
  109.     for(i=1;i<=N;i++)
  110.     {
  111.     makeset(i);
  112.     adj[i].clear();
  113.     }
  114.  
  115.     adj[i+1].clear();
  116.  
  117.     for(i=0;i<Q;i++)
  118.     {
  119.         cin>>a>>b>>type;
  120.         if(type==0)
  121.         {
  122.             joinset(a,b);
  123.         }
  124.         else
  125.         {
  126.             if(a==b)
  127.             {
  128.             flag=0;
  129.             }
  130.             v.push_back(make_pair(a,b));
  131.         }
  132.     }
  133.  
  134.     sizee=v.size();
  135.  
  136.     for(i=0;i<sizee;i++)
  137.     {
  138.         a=v[i].first;b=v[i].second;
  139.         repa=findrep(maap[a]);repb=findrep(maap[b]);
  140.  
  141.         if(repa==repb)
  142.         {
  143.         flag=0;
  144.         break;
  145.         }
  146.  
  147.         adj[repa->data].push_back(repb->data);
  148.         adj[repb->data].push_back(repa->data);
  149.     }
  150.  
  151.     for(i=1;i<=N;i++)
  152.     {
  153.         if(!visited[i])
  154.         {
  155.             if(!isbipartite(i))
  156.             flag=0;
  157.         }
  158.     }
  159.  
  160.     if(flag==0)
  161.         cout<<"no"<<endl;
  162.     else
  163.         cout<<"yes"<<endl;
  164.  
  165.    }
  166.  return 0;
  167. }
  168.  
Success #stdin #stdout 0s 18904KB
comments (?)
stdin
copy 
4
2 2
1 1 0
1 2 1
2 3
1 1 0
1 2 1
2 1 0
3 2
2 2 0
2 3 1
3 3
1 2 1
2 3 1
1 3 1
stdout
copy 
yes
no
yes
no
https://ideone.com/OGDY8I
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!