题解 P3388 【【模板】割点(割顶)】

Michael_Li

2017-07-09 21:43:13

Solution

关于tarjan算法,一直有一个很大的争议,就是low[u]=min(low[u],dfn[v]); 这句话,如果改成low[u]=min(low[u],low[v])就会wa掉,但是在求强连通分量时却没有问题 根据许多大佬的观点,我想提出自己的一点看法,在求强连通分量时,如果v已经在栈中,那么说明u,v一定在同一个强连通分量中,所以到最后low[u]=low[v]是必然的,提前更新也不会有问题,但是在求割点时,low的定义有了小小的变化,不再是最早能追溯到的祖先,(因为是个无向图)没有意义,应该是最早能绕到的割点,为什么用绕到,是因为是无向边,所以有另一条路可以走,如果把dfn[v]改掉就会上翻过头,可能翻进另一个环中,所以wa掉,仅是本人的一些个人看法,不知道讲的对不对,请各位指教。 下面附上ac代码 ```cpp #include<cstdio> #include<algorithm> #define N (1000000+10) using namespace std; int a[N],nxt[N],head[N],dfn[N],low[N],cnt,k; bool cut[N],bst[N]; void add(int x,int y){ a[++k]=y; nxt[k]=head[x]; head[x]=k; } void tarjan(int u,int mr){ int rc=0; dfn[u]=low[u]=++cnt; for (int p=head[u];p;p=nxt[p]){ int v=a[p]; if (!dfn[v]){ tarjan(v,mr); low[u]=min(low[u],low[v]); if (low[v]>=dfn[u]&&u!=mr) cut[u]=true; if (u==mr) rc++; } low[u]=min(low[u],dfn[v]); } if (u==mr&&rc>=2) cut[mr]=true; } int main(){ int n,m,ans=0; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } for (int i=1;i<=n;i++){ if (!dfn[i]) tarjan(i,i); } //for (int i=1;i<=n;i++) printf("%d %d %d\n",i,dfn[i],low[i]); for (int i=1;i<=n;i++) if (cut[i]) ans++; printf("%d\n",ans); for (int i=1;i<=n;i++) if (cut[i]) printf("%d ",i); } ```