Connecting Graph
Givennnodes in a graph labeled from1ton. There is no edges in the graph at beginning.
You need to support the following method:
1.connect(a, b), add an edge to connect nodeaand node b. 2.query(a, b)`, check if two nodes are connected
Example
5 // n = 5
query(1, 2) return false
connect(1, 2)
query(1, 3) return false
connect(2, 4)
query(1, 4) return true
S： union find
将连接在一起的node分为一组，每组有一个node作为代表。father[]数组存储每个节点对应的组代表节点，初始为0表示其组代表为自己。find()函数查找元素所在组的组代表节点，并压缩路径。
class ConnectingGraph {
public:
ConnectingGraph(int n) {
father = vector<int>(n + 1, 0);
}
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
}
}
bool query(int a, int b) {
return find(a) == find(b);
}
int find(int x) {
if (father[x] == 0) {
return x;
}
return father[x] = find(father[x]);
}
private:
vector<int> father;
};
Connecting Graph II
Givennnodes in a graph labeled from1ton. There is no edges in the graph at beginning.
You need to support the following method:
1.connect(a, b), an edge to connect node a and node b
2.query(a), Returns the number of connected component nodes which include nodea
Example
5 // n = 5
query(1) return 1
connect(1, 2)
query(1) return 2
connect(2, 4)
query(1) return 3
connect(1, 4)
query(1) return 3
S: 用一个额外的数组存储每个“老大哥”集合中的元素个数
class ConnectingGraph2 {
public:
ConnectingGraph2(int n) {
father = vector<int>(n + 1, 0);
size = vector<int>(n + 1, 1);
}
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
size[root_b] += size[root_a];
size[root_a] = size[root_b];
}
}
int query(int a) {
return size[find(a)];
}
int find(int x) {
if (father[x] == 0) {
return x;
}
return father[x] = find(father[x]);
}
private:
vector<int> father;
vector<int> size;
};
Connecting Graph III
Givennnodes in a graph labeled from1ton. There is no edges in the graph at beginning.
You need to support the following method:
1.connect(a, b), an edge to connect node a and node b
2.query(), Returns the number of connected component in the graph
Example
5 // n = 5
query() return 5
connect(1, 2)
query() return 4
connect(2, 4)
query() return 3
connect(1, 4)
query() return 3
S: 用一个额外变量count存储当前集合个数，每进行一次成功合并count减一
class ConnectingGraph3 {
public:
ConnectingGraph3(int n) {
count = n;
father = vector<int>(n + 1, 0);
}
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
count--;
}
}
int query() {
return count;
}
int find(int x) {
if (father[x] == 0) {
return x;
}
return father[x] = find(father[x]);
}
private:
vector<int> father;
int count;
};
323. Number of Connected Components in an Undirected Graph
Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
0 3
| |
1 --- 2 4
Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2.
Example 2:
0 4
| |
1 --- 2 --- 3
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1.
Note:
You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.
S: Union Graph
class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
father = vector<int>(n, -1);
count = n;
for (const auto& edge : edges) {
connect(edge.first, edge.second);
}
return count;
}
int find(int x) {
if (father[x] == -1) {
return x;
}
return father[x] = find(father[x]);
}
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
count--;
father[root_a] = root_b;
}
}
private:
vector<int> father;
int count;
};
Find the Weak Connected Component in the Directed Graph
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.)
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}
S: Union Find
因为输入是单向链接，结果是无向结果，用DFS不如用union find方便，因为union find不会受方向影响
/**
* 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) {
for (const auto& node : nodes) {
father[node->label] = node->label;
}
for (const auto& node : nodes) {
for (const auto& child : node->neighbors) {
connect(child->label, node->label);
}
}
return getResult();
}
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
}
}
int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
vector<vector<int>> getResult() {
vector<vector<int>> result;
unordered_map<int, vector<int>> map;
for (const auto& i : father) {
map[find(i.first)].push_back(i.first);
}
for (const auto& i : map) {
vector<int> nodes = i.second;
sort(nodes.begin(), nodes.end());
result.push_back(nodes);
}
return result;
}
private:
unordered_map<int, int> father;
};