Competitive Coding

This is the solution to this UVa problem Code #include <iostream> #include <iostream> #include<bits/stdc++.h> #define pb push_back #define T 50005 using namespace std; int p[T]; int r[T]; void ini(int n){ for(int i=0;i<n;i++){ p[i]=i; r[i]=1; } } int root(int a){ while(p[a]!=a){ p[a]=p[p[a]]; a=p[a]; } return a; } void joint(int a,int b){ if (a==b) return; a=root(a); b=root(b); if (a == b) return; if(r[a]>r[b]){ r[a]+=r[b]; p[b]=a; return; } r[b]+=r[a]; p[a]=b; } bool query(int a, int b){ return p[a]==p[b]; } int main() { std::ios::sync_with_stdio(false); int breaker; cin>>breaker; int test=0; while(1){ test++; if(test>breaker) break; int n,m; cin >> n>>m; if(n==0 && m==0) break; ini(n); while(m--){ int i,j; cin>>i>>j; joint(i-1,j-1); } int counter=0; int maxi=0; for(int i =0;i<n;i++){ maxi=max(maxi,r[i]); } cout&

This is the solution to this UVa problem Code

#include <iostream> #include <iostream> #include<bits/stdc++.h> #define pb push_back #define T 10005 using namespace std; int p[T]; int r[T]; void ini(int n){ for(int i=0;i<n;i++){ p[i]=i; r[i]=1; } } int root(int a){ while(p[a]!=a){ p[a]=p[p[a]]; a=p[a]; } return a; } void j(int a,int b){ if (a==b) return; a=root(a); b=root(b); if (a == b) return; if(r[a]>r[b]){ r[a]+=r[b]; p[b]=a; return; } r[b]+=r[a]; p[a]=b; } bool con(int a, int b){ return p[a]==p[b]; } int main() { std::ios::sync_with_stdio(false); return 0; }

This is the solution to this UVa problem . Note: In this problem you need to be very careful with the update of the rank list

Here is my implementation of Union Find with Path Compression in Python.

This is simple in-degree counting problem. I decided to use Python 3 for this question due to the split method available in strings.