题目
原题在此
解析
用dfs解题TLE了, 查了一下并查集的解法, 通过了. 链接在此
代码
c++/dfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> colors(n, 0);
for (int i = 0; i < n; ++i)
if(!colors[i] && !dfs(colors, graph, i, 1)) return false;
return true;
}
bool dfs(vector<int> colors, vector<vector<int>>& graph, int node, int color) {
if(colors[node]) return colors[node] == color;
colors[node] = color;
for (auto nei : graph[node])
if (!dfs(colors, graph, nei, -color)) return false;
return true;
}
};
|
c++/disjointSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class DisjointSet {
private:
vector<int> parent;
vector<int> rank;
public:
DisjointSet(int n) {
parent = vector<int>(n);
for(int i = 0; i < n; ++i) parent[i] = i;
rank = vector<int>(n, 1);
}
int find(int p) {
int t = p;
while(t != parent[t]) t = parent[t];
parent[p] = t;
return t;
}
void unionSet(int a, int b) {
int sa = find(a), sb = find(b);
if(sa == sb) return;
if(rank[sa] < rank[sb]) swap(sa, sb);
rank[sa] += rank[sb];
parent[sb] = sa;
}
};
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
if(!n) return false;
DisjointSet ds(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < graph[i].size(); ++j) {
if (ds.find(i) == ds.find(graph[i][j])) return false;
if (j) ds.unionSet(graph[i][j], graph[i][j - 1]);
}
}
return true;
}
};
|