Find the Weak Connected Component in the Directed Graph (ladder)

Description

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}

Assumption

use bfs/dfs? No, may miss CEF as the example Union Find? Yes, Compress Path? Yes,

Link

Lintcode_ladder

Method

1. union find, with Compress Path reaching o(1) find/union
2. x

Example

1. 1

code
/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param nodes a array of directed graph node
     * @return a connected set of a directed graph
     */
    vector<vector<int>> connectedSet2(vector<DirectedGraphNode*>& nodes) {
        // Write your code here
        vector<vector<int>> result;
        if (nodes.empty()) {
            return result;
        }
        unordered_map<int, int> dict;
        dictInit(dict, nodes);
        int len = nodes.size();
        for (int i = 0; i < len; ++i) {
            vector<DirectedGraphNode*>& neighbors = nodes[i]->neighbors;
            int n = neighbors.size();
            for (int j = 0; j < n; ++j) {
                dictUnion(dict, nodes[i]->label, neighbors[j]->label);
            }
        }
        unordered_map<int, vector<int>> map;
        for (int i = 0; i < len; ++i) {
            int child = nodes[i]->label;
            int father = dictFind(dict, child);
            if (map.find(father) == map.end()) {
                vector<int> row;
                //row.push_back(father);
                row.push_back(child);
                map[father] = row;
            } else {
                map[father].push_back(child);
            }
        }
        for (auto& element : map) {
            result.push_back(element.second);
        }
        return result;
    }
    // init union find, let everyone points to itself
    void dictInit(unordered_map<int, int>& dict, vector<DirectedGraphNode*>& nodes) {
        int len = nodes.size();
        for (int i = 0; i < len; ++i) {
            int label = nodes[i]->label;
            dict[label] = label; 
        }
    }
    // union child1 and child2, give it common father
    void dictUnion(unordered_map<int, int>& dict, int child1, int child2) {
        int fa1 = dictFind(dict, child1);
        int fa2 = dictFind(dict, child2);
        if (fa1 != fa2) {
            dict[fa2] = fa1;
        }
    }
    // find, get the root father
    int dictFind(unordered_map<int, int>& dict, int child) {
        int parent = dict[child];
        while (parent != dict[parent]) {
            parent = dict[parent];
        }
        // compress path
        // make all middle node points to the final parent
        int temp = -1;
        int father = dict[child];
        while (father != dict[father]) {
            temp = dict[father];
            dict[father] = parent;
            father = temp;
        }
        return parent;
    }
};

Similar problems

x

Tags

x