模板——tarjan求割点

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

注意求割点中的low定义：

割点中low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小）

当(u,v)为树边且low[v] >= dfn[u]时，节点u才为割点。该式子的含义：以节点v为根的子树所能追溯到最早的祖先节点要么为v要么为u。

根节点需要特判，若图不保证联通，要搜索多次

如果搜到已访问的点且不是父节点，就把low赋值为搜到点的dfn，下面程序可以证明这是正确的

但如果把low赋值为搜到点的low，就有可能影响其父亲的后面low更新（该点搜到它父亲的父亲，导致其父亲的low更新为父亲的父亲的low，这样就违背了low[u]不通过u父亲的原则）

详见样例：

5 6
1 2
1 3
2 3
3 4
4 5
3 5

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=;

 vector<int> v[];

 int n,m;

 int dfn[N],low[N],cnt=,vis[N],bl[N],tot=;

 void dfs(int u,int f)

 {

     int ch=;

     dfn[u]=++cnt;

     low[u]=cnt;

     vis[u]=;

     for(int i=;i<(int)v[u].size();i++)

     {

         int p=v[u][i];

         if(vis[p])

         {

             if(p!=f) low[u]=min(low[u],dfn[p]);

             //因为搜到u的点f必定肯定dfn最为接近于dfn[u]，故dfn[p]<dfn[f]，所以只需赋值成dfn[p]

             //搜索顺序一定是p->f->u，若f>p，则应是p搜到u(按照dfs顺序)

             //强连通就需要 low[u]=min(low[u],low[p]);

         }

         else

         {

             ch++;

             dfs(p,u);

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

             if(f==-&&ch>=) bl[u]=;

             if(f!=-&&low[p]>=dfn[u]) bl[u]=;

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

     {

         int x,y;

         scanf("%d%d",&x,&y);

         v[x].push_back(y);

         v[y].push_back(x);

     }

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

     {

         if(!vis[i]) dfs(i,-);//不一定是连通图

     }

     for(int i=;i<=n;i++) tot+=bl[i];

     cout<<tot<<endl;

     for(int i=;i<=n;i++) if(bl[i]) printf("%d ",i);

 }

巴特西

模板——tarjan求割点

最新文章

热门文章