tarkjan求无向图割点模板

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int n,m;

 const int maxn=1e5+;

 const int maxm=maxn<<;

 struct node

 {

     int to;

     int nxt;

 }e[maxm];

 int head[maxn];

 int tot;

 int id;

 int root;

 int low[maxn];

 int num[maxn];

 bool vis[maxn];

 int pa[maxn];

 int cnt=;

 int art[maxn];

 void init()

 {

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

     tot=;

     id=;

     memset(low,-,sizeof(low));

     memset(num,-,sizeof(num));

     memset(vis,false,sizeof(vis));

     memset(pa,-,sizeof(pa));

     cnt=;

     memset(art,,sizeof(art));

 }

 void add(int u,int v)

 {

     e[tot].to=v;

     e[tot].nxt=head[u];

     head[u]=tot++;

 }

 void findArt(int u)

 {

     vis[u]=true;

     low[u]=num[u]=++id;

     for(int i=head[u];i!=-;i=e[i].nxt)

     {

         int v=e[i].to;

         //树边

         if(!vis[v])

         {

             pa[v]=u;

             findArt(v);

             if(low[v]>=num[u]&&u!=root)

             {

                 art[cnt++]=u;

             }

             low[u]=min(low[u],low[v]);

         }

         else if(pa[v]!=u) //回退边

         {

             low[u]=min(low[u],num[v]);

         }

     }

 }

 void printArt()

 {

     int tmp=;

     for(int i=head[root];i!=-;i=e[i].nxt)

     {

         if(pa[e[i].to]==root) tmp++;

     }

     if(tmp>=) art[cnt++]=root;

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

     {

         printf("%d ",art[i]);

     }

     puts("");

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         init();

         int u,v;

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

         {

             scanf("%d%d",&u,&v);

             add(u,v);

             add(v,u);

         }

         root=;

         findArt(root);

         printArt();

     }

     return ;

  } 

Tarkjan求无向图割点

http://www.cnblogs.com/llhthinker/p/4954082.html