题解 P3388 【【模板】割点（割顶）】

**所以图论的题给的难度都这么高吗= =** 一道割点的模板题，我这里是用的tarjan算法的思想，但是这题和tarjan不完全相同。 其实当时自己写的时候犯了一个低级错误，所以感觉习惯好还是很重要。 ···cpp ```cpp #include<cstdio> struct node{ int from,to; int next; }e[200010];//邻接表用来存储图 int root,len,n,m,sum,ans; int head[100010],dfn[100010],low[100010],vis[100010],poi[100010]; int rin(){//最常规的读入优化 char ch=getchar(); int sum=0; while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9'){ sum=sum*10+ch-'0'; ch=getchar(); } return sum; } int fmin(int a,int b){return a<b?a:b;}//用这个是因为个人习惯，代替min函数使用 void add(int x,int y){//邻接表增加无向边 e[++len].to=y; e[len].from=x; e[len].next=head[x]; head[x]=len; e[++len].to=x; e[len].from=y; e[len].next=head[y]; head[y]=len; } void tarjan(int u,int fa){//其实这题使用的并不是原版的tarjan而是做了一些改动 int son=0; vis[u]=1; dfn[u]=low[u]=++sum;//这个点现在查找过 for(int i=head[u];i!=0;i=e[i].next){//查找该点可以到达的点 int v=e[i].to; if(vis[v]==1&&v!=fa) low[u]=fmin(low[u],dfn[v]);//如果这个点已经到过并且v不是u的父节点就不是割点，只需要做low更新处理 else if(dfn[v]==0){//如果该点未到达就搜索，u作为v的父节点传递 tarjan(v,u); son++;//u的孩子数增加 low[u]=fmin(low[u],low[v]);//更新low if((fa==-1&&son>1)||(fa!=-1&&dfn[u]<=low[v])){//如果该点是根节点并且孩子数大于1，或者该点并不是根节点但是dfn[u]<=low[v]，这个点就是根节点 if (poi[u]==0) ans++;//ans记录割点的数量 poi[u]=1;//将u标记成割点 } } } vis[u]=2;//这里其实可加可不加，但是这样做循环次数会变少。 } void inpt(){//输入处理 n=rin(); m=rin(); for (int i=1;i<=m;i++){ int x,y; x=rin(); y=rin(); add(x,y);//加无向边 } } void work(){//工作处理 for (int i=1;i<=n;i++) if (!dfn[i])//因为这个题是不一定只有一个联通分量所以这样判断 tarjan(i,-1); } void outp(){//输出处理 printf("%d\n",ans);//输出ans for (int i=1;i<=n;i++) if (poi[i]) printf("%d ",i);//如果该点是割点就输出 printf("\n"); } int main(){ inpt(); work(); outp(); return 0; } ``` ··· --我当时错误的地方是我自己写的fmin出错了，我求最小值结果求的是最大值，23333--