Two Edge Connecte4d Graph
- Time : O(v + e)
- Space : O(v + e)
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
44
45
46
47
| #include <vector>
using namespace std;
void dfs(vector<vector<vector<int>>>& bccs, vector<vector<int>>& st, vector<int>& vis, vector<int>& mi, int& id, vector<vector<int>>& adj, int u, int par) {
mi[u] = vis[u] = id++;
for(auto& v : adj[u]) {
if(v == par) continue;
if(vis[u] > vis[v]) {
st.push_back({u, v});
}
if(vis[v]) {
mi[u] = min(mi[u], vis[v]);
} else {
dfs(bccs, st, vis, mi, id, adj, v, u);
mi[u] = min(mi[u], mi[v]);
if(mi[v] >= vis[u]) {
bccs.emplace_back();
while(!st.empty()) {
auto e = st.back(); st.pop_back();
bccs.back().push_back(e);
if(e[0] == u and e[1] == v) break;
}
}
}
}
}
bool twoEdgeConnectedGraph(vector<vector<int>> edges) {
int n = edges.size();
vector<vector<vector<int>>> bccs;
vector<vector<int>> st;
vector<int> vis(n), mi(n);
int id = 1;
for(int i = 0; i < n; i++) {
if(i and !vis[i]) return false;
if(!vis[i])
dfs(bccs, st, vis, mi, id, edges, i, -1);
}
for(auto& bcc : bccs)
if(bcc.size() == 1) return false;
return true;
}
|
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
44
45
46
47
48
49
50
51
| #include <vector>
using namespace std;
struct BccContext {
vector<vector<vector<int>>> bccs;
vector<vector<int>> st;
vector<int> vis, mi;
int id;
BccContext(int n) : id(1) {
vis = vector<int>(n);
mi = vector<int>(n);
}
};
void dfs(BccContext* ctx, vector<vector<int>>& adj, int u, int par) {
ctx->vis[u] = ctx->mi[u] = ctx->id++;
for(auto& v : adj[u]) {
if(v == par) continue;
if(ctx->vis[u] > ctx->vis[v]) {
ctx->st.push_back({u,v});
}
if(ctx->vis[v]) {
ctx->mi[u] = min(ctx->mi[u], ctx->vis[v]);
} else {
dfs(ctx, adj, v, u);
ctx->mi[u] = min(ctx->mi[u], ctx->mi[v]);
if(ctx->mi[v] >= ctx->vis[u]) {
ctx->bccs.emplace_back();
while(!ctx->st.empty()) {
auto e = ctx->st.back(); ctx->st.pop_back();
ctx->bccs.back().push_back(e);
if(e[0] == u and e[1] == v) break;
}
}
}
}
}
bool twoEdgeConnectedGraph(vector<vector<int>> edges) {
int n = edges.size();
BccContext* ctx = new BccContext(n);
for(int i = 0; i < n; i++) {
if(i and !ctx->vis[i]) return false;
if(!ctx->vis[i])
dfs(ctx, edges, i, -1);
}
for(auto& bcc : ctx->bccs)
if(bcc.size() == 1) return false;
return true;
}
|
