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
| namespace Articulation{
inline int read(){
register int a=0,f=1;register char c;
while((c=getchar())<'0')if(c=='-')f=-1;;
while(c>='0')a=a*10+(c^48),c=getchar();
return a*f;
}
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
int n,m,cnt,tot,in[MAXN],rt,head[MAXN],dfn[MAXN],low[MAXN],curr,stt,ans,a,b;
bool vis[MAXN],cut[MAXN];
stack<int> st;
struct Edge{
int f,t,nxt;
}edge[MAXM];
inline void add(int f,int t){
edge[++tot].f = f;
edge[tot].t = t;
edge[tot].nxt = head[f];
head[f] = tot;
}
inline void tarjan(int pos, int fa){
int child = 0;
st.push(pos);
dfn[pos]=low[pos] = ++cnt;
vis[pos] = true;
for (int i=head[pos];i;i=edge[i].nxt){
int v = edge[i].t;
if (v==fa) continue;
if (!dfn[v]){
tarjan(v,pos);
child++;
low[pos] = min(low[pos],low[v]);
if (!cut[pos] && ((rt==pos && child>=2) || (rt!=pos && low[v] >= dfn[pos]))) cut[pos] = true;
}else low[pos] = min(low[pos],dfn[v]);
}
}
inline void tarj(){
for (int i=1;i<=n;i++) if (!dfn[i]) rt=i,tarjan(i,i);
}
inline int num_of_points(){
int re = 0;
for (int i=1;i<=n;i++) if (cut[i]) re++;
return re;
}
inline void init();
inline void solve();
}
|
