PCL FEB 22 - Hawk & Thrones - Edutorial

editorial
, ,
1

PROBLEM NAME: Hawk & Thrones

DIFFICULTY : Medium

PREREQUISITES : DSU, Graphs

PROBLEM : In the dragonland there reigns N nobles numbered from 1 to N and there are M friendships between these nobles represented by a M pairs of integers. Hawk plans to invade all of these nobles and he plans to invade the dragonland in a certain order represented by an array order of length N where order[i] is the noble to be attacked on the ith day.
After a noble is defeated then all its friendships with other nobles vanishes.
Given that there are relationships among nobles they unite and represent different connected components as united territories and Hawk can handle at most C territories and if they become greater than C, they will capture Hawk’s Army.

TASK: Determine if Hawk can defeat all the nobles successfully in the given order.

CONSTRAINTS :
1 <= N <= 10^5
0 <= M <= min(N*(N-1)/2,10^5)
0 <= C<= N
1 <= order[i] <= N
1 <= Ai,Bi <= N

SAMPLE INPUT (1) :
5 4
1 2
2 5
2 3
3 4
1 3 2 5 4
2

SAMPLE OUTPUT (1) :
Hawk wins

HINTS :
Hint 1 :As this problem is about connected components, think can we use Union-find here ?
Hint 2 : As we know DSU allows us to add an edge but here we need to delete an edge . To handle this, think can we process the order[] array in reverse order ?

EXPLANATION :
Before going further, if you didn’t have any knowledge of DSU, I would recommend you to go through this guide to get yourself familiar with DSU first.

Now,As we know that with the help of DSU , we can’t delete an edge but we can add an edge. So, we process the order[] array in reverse order and add an edge(friendship) with the help of union method in DSU and count the connected components(count of territories). If at any moment the count of connected components exceeds given C , we’ll print “Hawk is captured” and after processing all the queries of order[] array if count of connected components do not exceeds C , then print “Hawk wins”

Intuition for processing in reverse order:

We know that , After processing complete order[] array , all the nobles gets defeated and their friendship vanishes.Now , if we start uniting them from reverse order, then we know that all the nobles that comes before them in order[] array are already defeated so , we can neglect their friendships which means we can freely add the friendships(edges) of current noble in our current territory( component).

Note: Remember the common practice for query problems: “process queries in the reverse order.

SOLUTION:

#include <bits/stdc++.h>
 
using namespace std;
 
int parent[100005];
int Size[100005] = {1};
 
void init()
{
    for (int i = 0; i < 100005; i++)
    {
        parent[i] = i; // Initially, every element is parent of itself
    }
}
 
// finding the representative of the component
int Find(int u)
{
    if (parent[u] == u)
        return u;
    // path compression
    return parent[u] = Find(parent[u]);
}
 
void Union(int u, int v)
{
 	v= Find(v);
	u = Find(u);
	if(Size[v] > Size[u]) swap(u, v);
	if(u == v)return;
Size[u] += Size[v];
parent[v] = u;
}
int32_t main()
{
 
    int n, m; // n = number of nobles, m = number of friendships
    cin >> n >> m;
    init();
 
    vector<vector<int>> adj(n + 1);
 
    for (int i = 0; i < m; i++)
    { // input all friendships
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    vector<int> order(n);
    for (int i = 0; i < n; i++)
    {
        cin >> order[i];
    }
    int c; // limit value
    cin >> c;
 
    int connected_comp = 0;
    set<int> s;// set to check if noble is visited before or not
    // At any instance, if any noble is not present --> it means we must have processed that noble before and envaded it
 
    // processing in reverse order
    for (int i = n - 1; i >= 0; i--)
    {
        int current_vertex = order[i];
        s.insert(current_vertex);
        connected_comp++;
        for (auto j : adj[current_vertex])
        {
            if (Find(j) != Find(current_vertex) && s.find(j) != s.end())
            {// if j and current_vertex belongs to different components and we have not visited j before which denotes noble j is not envaded before, hence we need to include it in current component
                Union(current_vertex, j);
                connected_comp--;
            }
        }
 
        if(connected_comp > c){// if count of connected components is greater than limit value
            cout << "Hawk is captured" << endl;
		return 0;
        }
    }
 
    cout << "Hawk wins" << endl;
}

TIME COMPLEXITY : O(NlogN)
N - for processing in reverse order
logN - for find() method

SPACE COMPLEXITY : O(N)

1 Like