# PROBLEM LINK

*Author:* Bhavya Dhingra

*Tester:* Sachin Singh

*Editorialist:* Naman Dhingra, Prateek Mishra

# DIFFICULTY

MEDIUM

# PREREQUISITES

# PROBLEM

Given two integers N and Q, denoting **no. of nodes** and **no. of queries** respectively. For every query, 3 integers denoting the type of edge(1 or 2) and the nodes u and v between which the edge is formed.

Determine whether after each query the structure of connected components in 2 graphs(telepathy-graph and linguistic-graph) are **Mixed** or **not**. Where Mixed means an edge is Linguistic if and only if an Edge if telepathy. 2 Nodes u,v are said to be connected linguistically or telepathically if there exist at least one linguistic or telepathic path between them respectively. Correspondingly, produce output **YES** or **NO** respectively.

# EXPLANATION

It is easy to see that after each query, we need to tell if the **structure of the connected components in the telepathy-graph and the linguistic-graph are the same or not**. To construct edges, we will use a disjoint set union. But how to check the above for each query?

Actually, it is quite easy to do. **Keep DSU only for the telepathy-graph**. For each

query of adding telepathy-edge, simply apply the join operation in the DSU. And for the linguistic edges, we keep a data structure, e.g. a queue, in which we will store the edges that need to be checked over the telepathy-graph. What does this mean?

It means that suppose we got a query to add a linguistic edge between a and b, we store this in our queue. Then, while checking if the connected component structure of both the graphs is the same or not, we will go through our queue and for each pair, we check if they both lie in the same component in the telepathy-graph. If they don’t, then we stop and answer with **NO**, else we remove this pair from the queue and keep continuing with the same step. If we **end up with an empty queue**, this means that the **connected structure of both the graphs is the same**, i.e., all the elements form the same connected components in both the graphs. So, in this case, we output **YES**.

# TIME COMPLEXITY

Suppose \alpha is the time for join operation in DSU, the amortized time

complexity for the problem is O(Q*\alpha).

# SOLUTION

## Setter's Solution

```
// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define sync \
{ \
ios_base ::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL); \
}
typedef pair<int,int> pii;
const int N=1e5+1;
int n,q,p[N];
queue<pii> s;
int root(int u)
{
if (p[u]!=u)
p[u]=root(p[u]);
return p[u];
}
void solve()
{
scanf("%d %d",&n,&q);
for (int i=1;i<=n;++i)
p[i]=i;
while (q--)
{
int u,v,w;
scanf("%d %d %d",&w,&u,&v);
if (w==2)
{
int ru=root(u),rv=root(v);
if (rv!=ru)
p[rv]=ru;
}
else
{
s.push({u,v});
}
int ok=0;
while (!s.empty())
{
int u=s.front().first,v=s.front().second;
int ru=root(u),rv=root(v);
if (ru!=rv)
{
ok=1;
cout<<"NO\n";
break;
}
s.pop();
}
if (!ok)
cout<<"YES\n";
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("Ip6.txt", "r", stdin);
freopen("Op6.txt", "w", stdout);
#endif
srand((unsigned int)time(NULL));
sync;
solve();
return 0;
}
```