强连通分量&缩点

1.强连通定义：在有向图中，如果两个点\(x\),\(y\)间存在一条\(x\)到\(y\)的路径，也存在一条\(y\)到\(x\)的路径，则称\(x\),\(y\)是强连通的

2.强连通图定义：如果有向图G的任意两个顶点都强连通，则称G是一个强连通图

3.强连通分量定义：有向图的极大强连通子图，称为强连通分量

我们可以来看一张图：

{4,2,3}，{2,4,1,5}都是强连通图，但强连通分量是{1,2,3,4,5}，特别地，一个点也是强连通分量

而缩点就是把强连通分量缩成一个点

代码及分析

\(dfn[x]\)：表示x的时间戳，也就是x是第几个被\(dfs\)到的

\(dfstime\)：表示时间戳

\(sta[]\)：模拟栈

\(vis[x]\)：记录x是否在栈中

\(low[x]\)：表示这个点以及其子孙节点连的所有点中dfn最小的值

\(sd[x]=y\)：表示缩点后，点x被缩点成点y

\(col[x]=y\)：表示点x属于第y个强连通分量（和\(sd[]\)有点不同

\(cnt[x]=y\)：记录第x个强连通分量中有y个点

以下简化于超好的tarjan博客+我自己的一点感悟

1. 为什么要\(low[x]=dfn[x]=++dfstime;\)呢，因为如果x的子孙没有连着它的祖先的边的话，那么，由于x的子孙一定比x更后dfs到所以x目前是最小的
2. \(sta[]\)的作用是u之后的所有点在u被回溯时，u和它栈后所有的点组成强连通分量，而u被回溯的前提就是它的子孙有边连着它
3. 由于我们是在回溯的时候记录\(low[]\)，而不是边dfs边记录，所以如果有u的子孙有指向祖先的边，那么直接弹出栈即可，因为dfs序更后的点一定已经处理好了
4. 如果遍历到一个点\(！dfn[y]\),就先对y进行dfs，然后\(low[x]=min(low[x],low[y]);\)根据\(low[x]\)的定义所以我们只要把\(low[x],low[y]\)比较
5. 如果一个点已经被弹掉了（\(！vis[y]且dfn[y]\)），那么这个店肯定不能和u构成强连通分量，因为它到不了u，因为如果可以，那么肯定不会满足出栈的条件
6. 如果在栈里，则这两个互相可达，说明强连通
7. 当我们dfs完u的所有子树时，u的low值肯定是不变的，那么如果\(dfn[u]=low[u]\)说明了什么?说明了u和它之下的所有结点没有边是指向u的祖先了所以u和它的子孙就已经构成了强连通分量,但这时你可能会有一个疑惑“假如也u的子孙也没有边连向u呢？”，那么u的子孙肯定先出栈了

void tarjan(int x){
  low[x]=dfn[x]=++dfstime;
  sta[++top]=x;vis[x]=1;//入栈并记录
  for(int i=head[x];i;i=nxt[i]{//遍历x能到的每一个点
    int y=ver[i];
    if(!dfn[y]){
      tarjan(y);//先dfs再记录
      low[x]=min(low[x],low[y]);
    }
    else if(vis[y]){
        low[x]=min(low[x],dfn[y]);
    }
  }
  if(dfn[x]==low[x]){//找到一个环，全部弹出栈
    while(sta[top]){
      sd[sta[top]]=x;
      vis[sta[top]]=0;
      if(x==sta[top]){top--;break;}
      val[x]+=val[sta[top]];
      --top;
    }
  }
}

但一遍\(tarjan\)并不能搜完所有的点

for(int i=1;i<=n;i++) 
      if(!dfn[i]) tarjan(i);
  for(int i=1;i<=m;i++){
    int x=sd[from1[i]],y=sd[ver1[i]];
    if(x!=y) add(x,y);
  }

均摊下来每个点只会被遍历一遍

所以复杂读为\(O(n)\)

割点

割点的判定有两种情况：

1. u为树根，而且u有多于两个的子树。因为这些子树之间不会有边相连。
2. u不为树根，但满足\(low[y]>=dfn[x]且x!=root\)，因为这说明了y及其子树不能到达x的祖先

割点代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=2e+5;
int ver[N],head[N],nxt[N],tot,n,m;
int low[N],dfstime,dfn[N],cut[N],ans;
inline int read(){
  int x=0,f=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
  return x*f;
}
inline void add(int x,int y){
  ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
  ver[++tot]=x,nxt[tot]=head[y],head[y]=tot;
}
inline void tarjan(int x,int root){
  low[x]=dfn[x]=++dfstime;
  int child=0;
  for(int i=head[x];i;i=nxt[i]){
    int y=ver[i];
    if(!dfn[y]){
      tarjan(y,root);
      low[x]=min(low[x],low[y]);
      if(low[y]>=dfn[x]&&x!=root) cut[x]=1;//不为树根的情况
      if(x==root) child++;
    }
    low[x]=min(low[x],dfn[y]);
  }
  if(child>=2) cut[x]=1;//为树根的情况,等root的子树全部被搜完
}
int main(){
  n=read();m=read();
  for(int i=1,x,y;i<=m;i++){
    x=read();y=read();
    add(x,y);
  }
  for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
  for(int i=1;i<=n;i++){
    if(cut[i]) ans++;
  }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
      if(cut[i]) cout<<i<<" ";
    }
  return 0;
}