fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <math.h>
  5. #include <map>
  6. #include <set>
  7. #include <queue>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <string.h>
  11.  
  12. #define ll long long int
  13. #define l long int
  14. #define pi pair<int,int>
  15. #define pl pair<l,l>
  16. #define pll pair<ll,ll>
  17. #define mem0(a) memset(a,0,sizeof(a))
  18. #define mem1(a) memset(a,-1,sizeof(a))
  19. #define MOD 1000000007
  20. #define loop(i,n) for(int i=0;i<n;i++)
  21. #define loop1(i,n) for(int i=1;i<=n;i++)
  22. #define fast_input cin.tie(0);ios_base::sync_with_stdio(0);
  23.  
  24. using namespace std;
  25. int parent[100005];
  26. int siz[100005];
  27. int root(int i)
  28. {
  29.     while(parent[i]!=i)
  30.     {
  31.         parent[i]=parent[parent[i]];
  32.         i = parent[i];
  33.     }
  34.     return i;
  35. }
  36.  
  37. void unionn(int x,int y)
  38. {
  39.     int root_x = root(x);
  40.     int root_y = root(y);
  41.     if(siz[root_x]<siz[root_y])
  42.     {
  43.         parent[root_x]=root_y;
  44.         siz[root_y]+=siz[root_x];
  45.     }
  46.     else
  47.     {
  48.         parent[root_y]=root_x;
  49.         siz[root_x]+=siz[root_y];
  50.     }
  51. }
  52. bool findd(int x,int y)
  53. {
  54.     if(root(x)==root(y))
  55.         return true;
  56.     else
  57.         return false;
  58. }
  59. int main()
  60. {
  61.     int n;
  62.     scanf("%d",&n);
  63.     int color[n];
  64.     vector <int> adj[n];
  65.     loop(i,n)
  66.     {
  67.         parent[i]=i;   ///initalising each member as its own parent ///
  68.         siz[i]=1;      /// size of each group initailly all 1 ///
  69.         color[i]=-1;   /// setting color -1 for all vertices ///
  70.     }
  71.     for(int i=0;i<n-1;i++)
  72.     {
  73.         int a,b;
  74.         scanf("%d %d",&a,&b);
  75.         adj[a].push_back(b);    /// building up the graph(tree)///
  76.         adj[b].push_back(a);
  77.     }
  78.     int q;
  79.     scanf("%d",&q);
  80.     while(q--)
  81.     {
  82.         int a,b,c;
  83.         scanf("%d %d %d",&a,&b,&c);
  84.         if(a==1)
  85.         {
  86.             color[b]=c;
  87.             for(int i=0;i<adj[b].size();i++)
  88.             {
  89.                 int curr = adj[b][i];        /// connecting with DSU ///
  90.                 if(color[curr]==color[b])    /// if color of neighbours are same///
  91.                 {
  92.                     unionn(curr,b);
  93.                 }
  94.             }
  95.         }
  96.         else
  97.         {
  98.             if(findd(b,c))               /// if connect via DSU yes  ///
  99.                 printf("YES\n");
  100.             else
  101.                 printf("NO\n");
  102.         }
  103.     }
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
3
0 1
1 2
7
1 0 11
2 0 1
2 0 2
1 2 12
1 1 11
2 0 1
2 0 2
stdout
copy 
NO
NO
YES
NO
https://ideone.com/yhk2Xb
language:
C++ (gcc 8.3)
created:
7 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!