How to do this type of question

[4z86RXSz]

College is a major part of life, it gives you new friends life experiences and other stuff, our chef has joined as a teacher in college and he is watching the fresher’s closely. There are N students in a class and they don’t know each other. Slowly they start talking to each other and form groups of friends. Chef wants to keep track of all the events for answering questions about the class to the principal.

There are 2 types of queries :

0 A B : The student with number A becomes friends with student with number B
1 X Y: You have to tell whether the student number X and student number Y are friends or not.
Note : If A is friends with B, and B is friends with C. That implies C is friends with A.

Input:
First line will contain N, the number of students in class.
Next line contains Q, number of queries.
Next Q lines contain 3 integers as per the query above.
Output:
For each query, of type 2 Print “YES”, if they are friends and “NO”, if they are not.

Constraints
1≤N≤100000
1≤Q≤100000
1≤A,B,X,Y≤N
Subtasks
30 points : 1≤N,Q≤1000
70 points : Original Constraints
Sample Input:
3
4
0 1 2
1 1 3
0 2 3
1 1 3

Sample Output:
NO
YES

I thought of doing it with a vector<set<ll>> or using map but there is some error in my
   programs and i think there must be some easier better way to do it I just can't think what  
 can you help me please
 

[tdp]

Hi, could you post the code you have so far? And what part do you need help with?

[4z86RXSz]

My code so far is this but it is giving WA for some test cases
I have made a vector set and as the value of a and b are given if they are not found in any
set I am inserting a new set otherwise I am insert the individual elements and merging both the sets

for example

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define re(n) for(ll i = 0 ; i < n ; i++)
#define ree(n) for(ll i = 0 ; i < n ; i++)
#define rep(i , j , n) for(ll i = j ; i < n ; i++)
#define per(i , j , n) for(ll i = j ; i >= n ; i--)
#define mod 1000000007
int main()
{
    SPEED;
    ll n;
    cin>>n;
    ll q;
    cin>>q;
    vector<set<ll>> vs;
    while(q--)
    {
        ll c,a,b;
        cin>>c>>a>>b;
        if(c==0)
        {
            int flag=0;
            int index=-1,indexb=-1;
          for(int i=0;i<vs.size();i++)
          {
            if(vs[i].find(a)!=vs[i].end())
            {
                index=i;
                vs[i].insert(b);
                flag=1;
            }
            if(vs[i].find(b)!=vs[i].end())
            {
                indexb=i;
                vs[i].insert(a);
                flag=1;
            }
          }
          if(flag==0)
          {
              set<ll> t;
              t.insert(a);
              t.insert(b);
              vs.push_back(t);
          }
          else if(index!=-1 && indexb!=-1&&index!=indexb)
          {
              for(auto it=vs[indexb].begin();it!=vs[indexb].end();++it)
                    vs[index].insert(*it);
            vs.erase(vs.begin()+indexb);
          }
        }
        else
        {
            int flag=0;
            for(int i=0;i<vs.size();i++)
            {
                if(vs[i].count(a) && vs[i].count(b))
                {
                    cout<<"YES"<<endl;
                    flag=1;
                    break;
                }
            }
            if(flag==0)
                cout<<"NO"<<endl;
        }
 
    }
    return 0;
}

I need to know which type of data structure can be used to do this problem this is the first time i have encountered such a problem.
data structure like if
a,b=1,2
it make 1->2
a,b=3,4
3->4
a,b=2,3
it joins both
1->2->3->4

[sc7]

why not simply use graph for connecting and bfs to see whether they are connected or not, seems pretty straightforward..

EDIT: looking at the time complexity, UNION-FIND would be a better option.