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

今天学了割点，就A了这道板子，比较难理解的地方就在于如果是根节点就要找两个点来满足low[y]>=dfn[x]，如果不是就只需找一个点来满足。Tarjan(i,i)中第一个i是开始搜索的点而第

二个i代表根节点，就是这棵搜索树的根，虽然一开始值是一样的，但x是要随着搜索向下找的，而根节点在搜索过程中不变。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define maxn 100010

 #define maxm 500010

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 struct node

 {

     int to,nex;

 }edge[*maxm];

 int dfn[maxn],low[maxn],st[maxn],inn[maxn],head[maxm],ans[maxn];

 int n,m,cnt,res,num;

 inline void add(int u,int v)

 {

     cnt++;

     edge[cnt].to=v;

     edge[cnt].nex=head[u];

     head[u]=cnt;

 }

 inline void Tarjan(int x,int root)

 {

     dfn[x]=low[x]=++num;

     int flag=;

     for(int i=head[x];i!=-;i=edge[i].nex)

     {

         int y=edge[i].to;

         if(!dfn[y])

         {

             Tarjan(y,root);

             low[x]=min(low[x],low[y]);

             if(low[y]>=dfn[x]&&x!=root) ans[x]=true;

             if(x==root) flag++;

         }

         else low[x]=min(low[x],dfn[y]);

     }

     if(x==root&&flag>=) ans[root]=true;

 }

 int main()

 {

     memset(head,-,sizeof(head));

     n=read();m=read();

     for(int i=;i<=m;i++)

     {

         int u,v;

         u=read();v=read();

         add(u,v);

         add(v,u);

     }

     for(int i=;i<=n;i++)

         if(!dfn[i])

             Tarjan(i,i);

     for(int i=;i<=n;i++)

         if(ans[i])

             res++;

     write(res);

     printf("\n");

     for(int i=;i<=n;i++)

         if(ans[i])

         {

             write(i);

             printf(" ");

         }

     return ;

 }

请各位大佬斧正（反正我不认识斧正是什么意思）

巴特西

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

最新文章

热门文章