C++ Problem On Disjoint Data Structures














































C++ Problem On Disjoint Data Structures



Problem on Disjoint Data Structures:

Owl Arena is hosting a fight competition and many owls decided to take part in it.

Strength of an owl is the number associated with that owl.

Rules of the competition are:

  • An owl wins if its strength is greater than that of another.
  • An owl can ask his friend to fight that match for him.

Note : If A and B are friends, and B and C are friends, then A and C are also friends.

Input:
First line contains the number of owls participating N and the number of connections M.
M lines follow.
Each line contains two integers u and v denoting that they are friends.
Next line contains Q, the number of queries.
Q lines follow.
Each line contains two integers u and v. You need to tell who wins.

Output:
In each query, output the number of the owl that will win the match. If the owls(u and v) are in the same friend circle, output TIE.

Constraints:
1 %u2264 N,M,Q %u2264 105
u,v %u2264 N

Problem Setter 

SAMPLE INPUT
 
7 3
1 2
3 4
1 7
4
1 2
5 6
3 7
1 5
SAMPLE OUTPUT
 
TIE
6
7
1
Explanation

1,2 and 7 are friends. 3 and 4 are friends. 5,6 and 7 have no friends. now,
First query: 1 and 2 : since both belong to the same friend circle, answer is a TIE.
Second: 5 and 6: since there is no friend of 5 and no friend of 6 and 6 has higher strength. 6 will win.
Third: 3 and 7: 3 has a friend 4 who has more strength than 3 and 7 has no friends whose strength is greater than his. so 4 vs 7. 7 will win.
Fourth: 1 and 5: 1 has a friend 7 who has more strength than 1 and 5 has no friends. so 5 vs 7. 7 will win. And since the fight was b/w 1 and 5. 1 wins the fight.

Implementation code for above problem:

#include<iostream>
using namespace std;
//For parent array
int a[100001];
int find(int f){
//if it is a parent
if(a[f]<0){
return f;
}
else{
return a[f]=find(a[f]);
}
}
void Union(int a1,int b1){
//assign element with larger value as parent to another
a[a1]=min(a[a1],a[b1]);
a[b1]=a1;
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
a[i]=-i;
}
int a1,b1;
for(int i=1;i<=k;i++){
cin>>a1>>b1;
int para=find(a1);
int parb=find(b1);
if(para!=parb){
Union(para,parb);
}
}
cin>>k;
for(int i=1;i<=k;i++){
cin>>a1>>b1;
int para=find(a1);
int parb=find(b1);
if(para==parb){
cout<<"TIE"<<endl;
}
else if(a[para]<a[parb]){
cout<<a1<<endl;
}
else{
cout<<b1<<endl;
}
}
}
---------------------------------------------------
Input:

7 3
1 2
3 4
1 7
4
1 2
5 6
3 7
1 5

Output:

TIE
6
7
1




More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 162 0
C++ Sieve Of Erastosthenes 135 0
C++ Gold Mine Problem 295 0
C++ Merge K Sorted Arrays 117 0
C++ K Centers Problem 240 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 285 0
C++ Find Non Repeating Elements in Array 87 0
C++ Merge Two Binary Trees 120 0
C++ Sum of Numbers From Root To Leaf Paths 89 0
C++ Meta Strings 91 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 199 0
C++ Smallest window with all characters in string 93 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 86 0
C++ Minimum characters added at front of string in palindrome conversion 69 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 75 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 113 0
C++ String Matching(KMP Algorithm) 140 0
C++ Remove Duplicates From String 110 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 86 0
C++ Problem On Disjoint Data Structures 95 0
C++ Disjoint Data Structures Part3 79 0
Disjoint Data Structures Part2 90 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 290 1
C++ Trie Datastructure 279 1
C++ Greedy Approach Minimum number of coins 525 0
C++ Greedy Approach Maximum height Pyramid 328 1
C++ Greedy Approach String lexicographically largest subsequence 246 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 458 1
C++ Greedy Approach N-array maximum sum 333 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 348 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 745 1
C++ Greedy Approach-Egyptian Fractions 639 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2

Comments