Find-the-Weak-Connected-Component.md

##Find the Weak Connected Component in the Directed Graph Show result

19% Accepted

Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)

Have you met this question in a real interview? Yes
Example
Given graph:

A----->B  C
 \     |  |
  \    |  |
   \   |  |
    \  v  v
     ->D  E <- F
Return {A,B,D}, {C,E,F}. Since there are two connected component which are {A,B,D} and {C,E,F}

Note
Sort the element in the set in increasing order

####Tags Expand

• Union Find

public class Solution {
	class UnionFind{
		HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
		UnionFind(HashSet<Integer> hashSet){
			for(Integer now : hashSet) {
				father.put(now, now);
			}
		}
        int find(int x){
        	int parent =  father.get(x);
        	while(parent!=father.get(parent)) {
        		parent = father.get(parent);
        	}
        	return parent;
        }
        int compressed_find(int x){
        	int parent =  father.get(x);
        	while(parent!=father.get(parent)) {
        		parent = father.get(parent);
        	}
        	int temp = -1;
        	int fa = father.get(x);
        	while(fa!=father.get(fa)) {
        		temp = father.get(fa);
        		father.put(fa, parent) ;
        		fa = temp;
        	}
        	return parent;

        }

        void union(int x, int y){
        	int fa_x = find(x);
        	int fa_y = find(y);
        	if(fa_x != fa_y)
        		father.put(fa_x, fa_y);
        }
	}
	List<List<Integer> >  print(HashSet<Integer> hashSet, UnionFind uf, int n) {
		List<List <Integer> > ans = new ArrayList<List<Integer>>();
        HashMap<Integer, List <Integer>> hashMap = new HashMap<Integer, List <Integer>>();
        for(int i : hashSet){
        	int fa = uf.find(i);
        	if(!hashMap.containsKey(fa)) {
        		hashMap.put(fa,  new ArrayList<Integer>() );
        	}
        	List <Integer> now =  hashMap.get(fa);
        	now.add(i);
        	hashMap.put(fa, now);
        }
        for( List <Integer> now: hashMap.values()) {
            Collections.sort(now);
        	ans.add(now);
        }
		return ans;
	}

	public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes){
        // Write your code here

		HashSet<Integer> hashSet = new HashSet<Integer>();
		for(DirectedGraphNode now : nodes){
			hashSet.add(now.label);
			for(DirectedGraphNode neighbour : now.neighbors) {
				hashSet.add(neighbour.label);
			}
		}
		UnionFind uf = new UnionFind(hashSet);


		for(DirectedGraphNode now : nodes){

			for(DirectedGraphNode neighbour : now.neighbors) {
				int fnow = uf.find(now.label);
	        	int fneighbour = uf.find(neighbour.label);
	        	if(fnow!=fneighbour) {
	        		uf.union(now.label, neighbour.label);
	        	}
			}
		}


        return print(hashSet , uf, nodes.size());
    }

}