Loading... Tarjan求割点 <!--more--> #### 割点判定法则 * 若x不是搜索树的根节点,则x是割点当且仅当搜索树上存在一个x的子节点y,满足:$dfn\[x\]\\leq low\[y\]$。 特别的,若x是搜索树的根节点,则x是割点当且仅当搜索树上至少存在两个子节点$y\_1,y\_2$满足此条件。 * 证明方法与求桥雷同。 * 因为判定是小于等于,所以求割点时,无需考虑父节点和重边的问题,从x出发访问的所有时间戳均可更新$low\[x\]$。 * * * #### 代码如下: #include<bits/stdc++.h> using namespace std; const int SIZE=100010; struct Edge{ int to,next; }e[SIZE*2]; int head[SIZE],n,m,tot,dfn[SIZE],low[SIZE],num,root,cnnt=0; bool u[SIZE]; void add(int x,int y){ e[++tot].to=y; e[tot].next=head[x]; head[x]=tot; } void tarjan(int x){ dfn[x] = low[x] = ++num; int cnt = 0; for(int i=head[x];i;i=e[i].next){ int y=e[i].to; if(!dfn[y]){ tarjan(y); low[x] = min(low[x], low[y]); if (low[y] >= dfn[x]) { cnt++; if (x != root || cnt > 1) u[x]=true; } } else low[x] = min(low[x], dfn[y]); } } int main(){ cin>>n>>m; tot=1; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; if(x==y) continue; add(x,y),add(y,x); } for(int i=1;i<=n;i++){ if(!dfn[i]) { root=i; tarjan(i); } } cnnt=0; for(int i=1;i<=n;i++){ if(u[i]) cnnt++; } cout<<cnnt<<endl; for(int i=1;i<=n;i++){ if(u[i]) cout<<i<<" "; } return 0; } Last modification:March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用,请随意赞赏