[LintCode][Union Find] Find the

Problem

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.)

Notice

Sort the element in the set in increasing order

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}

Solution

并查集

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    map<int, int> father;
public:
    /**
     * @param nodes a array of directed graph node
     * @return a connected set of a directed graph
     */
    vector<vector<int>> connectedSet2(vector<DirectedGraphNode*>& nodes) {
        for(int i = 0; i < nodes.size(); i++) {
            int label = nodes[i]->label;
            if (father.count(label) == 0) {
                father[label] = label;
            }
            
            for(int j = 0; j < nodes[i]->neighbors.size(); j++) {
                int neLabel = nodes[i]->neighbors[j]->label;
                father[findFather(neLabel)] = findFather(label);
            }
        }
        
        map<int, vector<int>> v;
        for(int i = 0; i < nodes.size(); i++) {
            int label = nodes[i]->label;
            v[findFather(label)].push_back(label);
        }
        
        vector<vector<int>> ret;
        for(map<int, vector<int>>::iterator iter = v.begin(); iter != v.end(); iter++) {
            ret.push_back(iter->second);
        }
        
        return ret;
    }
    
    int findFather(int label) {
        int startLabel = label;
        
        if (father.count(label) == 0) {
            father[label] = label;
            return label;
        }
        
        while (father[label] != label) {
            label = father[label];
        }
        
        while (father[startLabel] != startLabel) {
            int nextLabel = father[startLabel];
            father[startLabel] = label;
            startLabel = nextLabel;
        }
        
        return label;
    }
};