-
Notifications
You must be signed in to change notification settings - Fork 0
/
lowlink.hpp
42 lines (40 loc) · 1.13 KB
/
lowlink.hpp
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
#pragma once
struct LowLink{
const int n; vector<vector<int>> g;
vector<int> used,ord,low,id,arti;
LowLink(const int& _n=0):n(_n),g(n),
used(n,0),ord(n,0),low(n,0),id(n,-1){
}
void add_edge(int u,int v){
g[u].emplace_back(v); g[v].emplace_back(u);
}
void dfs(int v,int p,int& k){
used[v]=1; low[v]=ord[v]=k++;
bool isarti=0;
int cnt=0,sub=0;
for(auto& to:g[v]){
if(to==p and (++sub)<=1)continue;
if(!used[to]){
cnt++; dfs(to,v,k);
chmin(low[v],low[to]);
isarti|=(p>=0&&low[to]>=ord[v]);
}
else chmin(low[v],ord[to]);
}
isarti|=(p==-1&&cnt>1);
if(isarti)arti.push_back(v);
}
void dfs2(int v,int p,int& k){
if(p!=-1 and ord[p]>=low[v])id[v]=id[p];
else id[v]=k++;
for(auto& to:g[v])if(id[to]==-1)dfs2(to,v,k);
}
int run(){
int k=0; rep(i,0,n)if(!used[i])dfs(i,-1,k);
k=0; rep(i,0,n)if(id[i]==-1)dfs2(i,-1,k);
return k;
}
};
/**
* @brief Lowlink
*/