CCL4 - Editorial

editorial
, ,
1

PROBLEM LINK

Practice

Contest

Author: Bhavya Dhingra

Tester: Sachin Singh

Editorialist: Naman Dhingra, Prateek Mishra

DIFFICULTY

MEDIUM

PREREQUISITES

Disjoint Set Union

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;
}
2 Likes