#union-find

#include <iostream> using namespace std;

struct Edge {    int A;    int B;    int C; }; struct Edge *edge; int v,e,*root,*_rank; void quicksort(Edge a[], int first, int end) {   // edge들을 가중치 오름차순으로 정렬    int i=first, j=end;    Edge h;    int x = a[(first+end)/2].C;

   do {        while(a[i].C<x) i++;        while(a[j].C>x) j--;        if(i<=j) {            h=a[i];            a[i]=a[j];            a[j]=h;            i++;            j--;        }    } while(i<=j);    if(first<end) quicksort(a,first,j);    if(i<end) quicksort(a,i,end); }

int _find(int x) { if(root[x] == x) return x; // path compression return root[x] = _find(root[x]); } void _union(int x,int y) { int x_root = _find(x); int y_root = _find(y); if( x_root == y_root) return ;

// union_by-rank if(_rank[x_root] < _rank[y_root]) root[x_root] = y_root; else { root[y_root] = x_root; if(_rank[x_root] == _rank[y_root]) _rank[x_root]++; } } bool _check_graph(int x,int y) { if(_find(x) == _find(y)) return false; return true; } int _kruskal() { int i,weight=0; for(i=0;i<e;i++) { if(_check_graph(edge[i].A,edge[i].B)) { _union(edge[i].A,edge[i].B); weight+=edge[i].C; } } return weight; }

int main() { int i; cin >> v >> e; edge = new Edge[e]; root = new int[v+1]; _rank = new int[v+1]; for(i=1;i<=v;i++) root[i]=i,_rank[i]=0; for(i=0;i<e;i++) { cin >> edge[i].A >> edge[i].B >> edge[i].C; if(edge[i].A > edge[i].B) { int temp; temp=edge[i].A; edge[i].A = edge[i].B; edge[i].B = temp; } } quicksort(edge,0,e-1); cout << _kruskal() << endl; delete [] edge; delete [] root; delete [] _rank; }

vertax : max-10000 , edge: max-100000

Somehow I thought of union-find as a completely separate data structure from undirected graphs, and spent some time trying to figure out the difference. 

This week I focused on the union-find algorithm. You know, when you log into LinkedIn and you see that someone is separated from you by 3 degrees (a 3rd connection), LinkedIn is probably using union-find. Union-Find is an algorithm that "finds" whether 2 items are connected, and if not, can "union" them.

This algorithm comes in several flavors. One is Quick Find, where find is immediate, but the union operation grows quadratically. Another flavor is Quick Union, where union's performance depends on the ordering of the input data. Some orders are worse than others. Then there are a variety of flavors called Weighted Quick Union that guarantee union and find each grow logarithmically, which makes these flavors practical.

I really enjoyed playing around with understanding the performance of this algorithm by running experiments with random data. I wrote a python program that can compare 2 algorithms (like Quick Union and Weighted Union) or it can run experiments with a single algorithm to find out how it grows (quadratically, logarithmically, etc).  Given the number of trials, the algorithm(s), and the starting size N, the experiments double N at each trial and measure the running times. Cool to see how the numbers are so close to a formulla derived by mathematicians who have spent a long time studying this algorithm.

I also enjoyed writing a program to generate worse case data. Certain pairs of data, in a certain order, are worse case for the best Weighted Union variety. The pairs of data are input in an order such that the union of pairs builds trees. And the trees have a pattern: the number of elements at each level of tree is pascal's triangle. Cool.

Level 1Level 2Level 3Div 1Level 1Level 2Level 3Div 2Level 1Level 2Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Source Code:

Sivision Two - Level Three:

Solution

This is a Minimum Spanning Tree problem, which here is solved by using Union-Find algorithm, The only meaning thing in this disjoint-set data structure is parant[x], to identify if they are in the same group. The algorithm first collects all of the roads, then sorts them by cost and ID name as described in the statement, go through every road and check if the two connected cities are in the same group, if not, we get them in the same group by using union(x,y) function. At last, we need to check if every city is in the same group to show if this mission is possible to be finished. At the very last, every rebuild road ID needs to be sorted.

Source Code:

import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; /** * @author: antonio081014 */ public class RoadReconstruction { private HashMap<String, Integer> avai; public String selectReconstruction(String[] roads) { ArrayList<Road> list = new ArrayList<Road>(); avai = new HashMap<String, Integer>(); for (int i = 0, index = 0; i < roads.length; i++) { String[] str = roads[i].split(" "); int a, b; if (avai.get(str[1]) == null) { a = index++; avai.put(str[1], a); } else a = avai.get(str[1]); if (avai.get(str[2]) == null) { b = index++; avai.put(str[2], b); } else b = avai.get(str[2]); if (str.length == 3) { list.add(new Road(str[0], str[1], str[2], 0)); } else { list.add(new Road(str[0], str[1], str[2], Integer .parseInt(str[3]))); } } Collections.sort(list); UnionFind set = new UnionFind(100); List<String> retList = new ArrayList<String>(); for (int i = 0; i < list.size(); i++) { String id = list.get(i).id; String c1 = list.get(i).city1; String c2 = list.get(i).city2; int a = avai.get(c1); int b = avai.get(c2); if (set.find(a) != set.find(b)) { set.union(a, b); if (list.get(i).cost != 0) retList.add(id); } } for (Map.Entry<String, Integer> entry : avai.entrySet()) { // System.out.println(entry.getKey()); // System.out.println(entry.getValue()); if (set.find(entry.getValue()) != set.find(0)) return "IMPOSSIBLE"; } if (retList.size() == 0) return ""; Collections.sort(retList); String ret = retList.get(0); for (int i = 1; i < retList.size(); i++) ret += " " + retList.get(i); return ret; } } class Road implements Comparable<Road> { public String id; public String city1; public String city2; public int cost; public Road(String id, String c1, String c2, int cost) { this.id = id; this.city1 = c1; this.city2 = c2; this.cost = cost; } public int compareTo(Road a) { if (this.cost != a.cost) return this.cost - a.cost; return this.id.compareTo(a.id); } } class UnionFind { int N; int[] parent; public UnionFind(int n) { this.N = n; parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } } public int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } public void union(int x, int y) { int r1 = find(x); int r2 = find(y); if (r1 == r2) return; parent[r1] = r2; } }

Division Two - Level Two:

Solution

Source Code:

Division Two - Level One:

Solution

Problem Links:

UVa10158,

Problem:

Problem B: War

    A war is being lead between two countries, A and B. As a loyal citizen of C, you decide to help your country’s espionage by attending the peace-talks taking place these days (incognito, of course). There are n people at the talks (not including you), but you do not know which person belongs to which country. You can see people talking to each other, and through observing their behaviour during their occasional one-to-one conversations, you can guess if they are friends or enemies. In fact what your country would need to know is whether certain pairs of people are from the same country, or they are enemies. You may receive such questions from C’s government even during the peace-talks, and you have to give replies on the basis of your observations so far. Fortunately nobody talks to you, as nobody pays attention to your humble appearance.

  Abstract

    Now, more formally, consider a black box with the following operations:

               setFriends(x, y)     shows that x and y are from the same country

               setEnemies(x, y)   shows that x and y are from different countries

               areFriends(x, y)     returns true if you are sure that x and y are friends

               areEnemies(x, y)   returns true if you are sure that x and y are enemies

    The first two operations should signal an error if they contradict with your former knowledge. The two relations ‘friends’ (denoted by ~) and ‘enemies’ (denoted by *) have the following properties:

              ~ is an equivalence relation, i.e.

1.      If x ~ y and y ~ z then x ~ z  (The friends of my friends are my friends as well.)

2.      If x ~ y then y ~ x                  (Friendship is mutual.)

3.      x ~ x                                       (Everyone is a friend of himself.)

              * is symmetric and irreflexive

4.      If x * y then y * x                  (Hatred is mutual.)

5.      Not x * x                                (Nobody is an enemy of himself.)

              Also

6.      If x * y and y * z then x ~ z   (A common enemy makes two people friends.)

7.      If x ~ y and y * z then x * z   (An enemy of a friend is an enemy.)

    Operations setFriends(x, y) and setEnemies(x, y) must preserve these properties.

  Input

     The first line contains a single integer, n, the number of people.

     Each of the following lines contains a triple of integers, c x y, where c is the code of the operation:

            c = 1, setFriends

            c = 2, setEnemies

            c = 3, areFriends

            c = 4, areEnemies

     and x and y are its parameters, which are integers in the range [0, n), identifying two (different) people. The last line contains 0 0 0.

    All integers in the input file are separated by at least one space or line break.

  Output

     For every ‘areFriends’ and ‘areEnemies’ operation write 0 (meaning no) or 1 (meaning yes) to the output. Also for every ‘setFriends’ or ‘setEnemies’ operation which contradicts with previous knowledge, output a –1 to the output ; note that such an operation should produce no other effect and execution should continue. A successful ‘setFriends’ or ‘setEnemies’ gives no output.

    All integers in the output file must be separated by at least one space or line break.

  Constraints

    n < 10000, the number of operations is unconstrained.

  Sample Input

            10

            1 0 1

            1 1 2

            2 0 5

            3 0 2

            3 8 9

            4 1 5

            4 1 2

            4 8 9

            1 8 9

            1 5 2

            3 5 2

            0 0 0

  Sample Output

            1

            0

            1

            0

            0

            -1

            0

Source Code:

Using Union-Find data structure, Parent tells the root of the tree, while rank tells which side it is on.