如何求割点呢？鉴于此问题的简单，就由小华来解答一下！
小华（揉揉眼睛）：呃……这道题目嘛！太简单了，我表示不屑于做！
小明：老师，他刚刚在睡觉，没听讲，连你问什么都不知道。
小华：你……我不和你玩了！！！！！！！
老师：那小明回答一下。
小明：啊！我也不会！换小猫来吧，她最厉害了。
小猫(极不情愿)：遇事就叫我……下面是我的代码，不解释了。
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=10005; vector<int >p[N]; int fl[N],dfn[N],low[N]; int num,tot; void tarjan(int x,int root){ dfn[x]=low[x]=++num; for(int i=0;i<p[x].size();++i){ int v=p[x][i]; if(!dfn[v]){ tarjan(v,root); low[x]=min(low[x],low[v]); if(dfn[x]<=low[v]&&x!=root)fl[x]=1; if(x==root)tot++; } low[x]=min(low[x],dfn[v]); } if(x==root&&tot>=2)fl[root]=1; } int main(){ int n,m,x,y; cin>>n>>m; for(int i=1;i<=m;++i){ cin>>x>>y; p[x].push_back(y); p[y].push_back(x); } for(int i=1;i<=n;++i) if(!dfn[i])tarjan(i,i); int ans=0; for(int i=1;i<=n;++i) if(fl[i])ans++; printf("%d\n",ans); for(int i=1;i<=n;++i) if(fl[i]) printf("%d ",i); return 0; }
老师：小猫果然厉害，但是美中有个不足之处。
小猫：老师，我看到错误了。就是那个tot放错位置了。应该是：
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=10005; vector<int >p[N]; int fl[N],dfn[N],low[N]; int num; void tarjan(int x,int root){ int tot=0;//因为每次都要置零…… dfn[x]=low[x]=++num; for(int i=0;i<p[x].size();++i){ int v=p[x][i]; if(!dfn[v]){ tarjan(v,root); low[x]=min(low[x],low[v]); if(dfn[x]<=low[v]&&x!=root)fl[x]=1; if(x==root)tot++; } low[x]=min(low[x],dfn[v]); } if(x==root&&tot>=2)fl[root]=1; } int main(){ int n,m,x,y; cin>>n>>m; for(int i=1;i<=m;++i){ cin>>x>>y; p[x].push_back(y); p[y].push_back(x); } for(int i=1;i<=n;++i) if(!dfn[i])tarjan(i,i); int ans=0; for(int i=1;i<=n;++i) if(fl[i])ans++; printf("%d\n",ans); for(int i=1;i<=n;++i) if(fl[i]) printf("%d ",i); return 0; }
老师：小猫解释一下，为什么放外面不行。
小猫：由于每次都要更新根的子树个数，所以每次都要把它置零，放外面也行，但还是要更新tot的值，所以直接放里面更好。
老师：就是这样，还有什么问题吗？（读者有问题可以评论）
