Friday, July 22, 2016
C++ Solution to UVA 10608 - Friends Union by Rank and Path Compression
July 22, 2016
10608 friends
,
algorithm explanation
,
algorithm to cpp implementation
,
c++
,
commented code
,
disjoint set count
,
friends solution
,
made easy
,
path compression
,
union by rank
,
uva 10608
Problem Link:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1549These are my old codes I kept for visual explanations but I lost all the data. Since these are old codes I can not remember if I made any breaking changes to the code later. For the algorithm please see Introduction to Algorithms book.
Problem Explanation & Visalization:
TODOInput & Output Explanation:
TODOInput & Output:
Input:2 3 2 1 2 2 3 10 12 1 2 3 1 3 4 5 4 3 5 4 6 5 2 2 1 7 1 1 2 9 10 8 9
Output:3 7
More input and output in udebug:
https://www.udebug.com/UVa/10608Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Author: Asif Ahmed | |
| * Site: https://quickgrid.wordpress.com | |
| * Problem: UVA 10608 - Friends | |
| * Technique: Disjoint-Set Forest Union by Rank | |
| * and Path Compression using Structure. | |
| */ | |
| #include<stdio.h> | |
| #include<string.h> | |
| #define N 100000 | |
| static int parentArray[N]; | |
| static int rankArray[N]; | |
| static int elementsArray[N]; | |
| int maximum; | |
| // Basically create n sets with elements from | |
| // 0 to n - 1. Reset their rank to 0 since the | |
| // sets have only one element. So each set is | |
| // basically pointing to itself in the parent | |
| // array. | |
| void MakeSet(int n){ | |
| for(int i = 0; i < n; ++i){ | |
| parentArray[i] = i; | |
| rankArray[i] = 0; | |
| elementsArray[i] = 1; | |
| } | |
| } | |
| // Find the parent of the node and | |
| // do path compression in the process. | |
| int FindSet(int x){ | |
| if( x != parentArray[x] ) | |
| parentArray[x] = FindSet( parentArray[x] ); | |
| return parentArray[x]; | |
| } | |
| // Check if both elements are in the same set. | |
| bool SameSet(int x, int y){ | |
| return FindSet(x) == FindSet(y); | |
| } | |
| // Check if they are already in the same set. | |
| // If not then the tree or Set with the bigger | |
| // rank becomes the parent of tree with smaller | |
| // rank. | |
| // If both have same rank then arbitrarily choose | |
| // one to be the parent of the other set. Here y | |
| // is chosen. | |
| void Link(int x, int y){ | |
| if( !SameSet(x, y) ){ | |
| if( rankArray[x] > rankArray[y] ){ | |
| parentArray[y] = x; | |
| elementsArray[x] += elementsArray[y]; | |
| maximum = ( maximum < elementsArray[x] ) ? elementsArray[x] : maximum; | |
| } | |
| else{ | |
| parentArray[x] = y; | |
| elementsArray[y] += elementsArray[x]; | |
| maximum = ( maximum < elementsArray[y] ) ? elementsArray[y] : maximum; | |
| if(rankArray[x] == rankArray[y]) | |
| rankArray[y] = rankArray[y] + 1; | |
| } | |
| } | |
| } | |
| // Union two sets. | |
| // First find their representative and link them. | |
| void Union(int x, int y){ | |
| Link( FindSet(x), FindSet(y) ); | |
| } | |
| int main(){ | |
| //freopen("input.txt", "r", stdin); | |
| //freopen("output.txt", "w", stdout); | |
| int n, m; | |
| int i, j; | |
| int times; | |
| scanf("%d", ×); | |
| while( times-- ){ | |
| scanf("%d%d", &n, &m); | |
| MakeSet(n); | |
| maximum = 1; | |
| while(m--){ | |
| scanf("%d%d", &i, &j); | |
| --i, --j; | |
| Union(i, j); | |
| } | |
| printf("%d\n", maximum); | |
| } | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment