Friday, July 22, 2016
C++ Solution to UVA 10583 - Ubiquitous Religions Union by Rank and Path Compression
July 22, 2016
algorithm explanation
,
algorithm to cpp implementation
,
c++
,
commented code
,
disjoint set count
,
made easy
,
path compression
,
Ubiquitous Religions solution
,
union by rank
,
uva 10583
Problem Link:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1524These 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:10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 4 2 3 4 5 4 8 5 8 0 0
Output:Case 1: 1 Case 2: 7
More input and output in udebug:
https://www.udebug.com/UVa/10583Code:
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 10583 - Ubiquitous Religions | |
| * 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]; | |
| int disjointSetCount; | |
| // 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; | |
| } | |
| disjointSetCount = n; | |
| } | |
| // 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; | |
| else{ | |
| parentArray[x] = y; | |
| if(rankArray[x] == rankArray[y]) | |
| rankArray[y] = rankArray[y] + 1; | |
| } | |
| --disjointSetCount; | |
| } | |
| } | |
| // 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 caseNumber = 0; | |
| while( scanf("%d%d", &n, &m) && n && m ){ | |
| MakeSet(n); | |
| while(m--){ | |
| scanf("%d%d", &i, &j); | |
| Union(i, j); | |
| } | |
| printf("Case %d: %d\n", ++caseNumber, disjointSetCount); | |
| } | |
| return 0; | |
| } |
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment