无向图

• 割点：删除x和与x相连的边，图不再连通，x为割点
• 割边：删去该边e，图不再连通，e为割边
• 点双连通分量：其本身不存在割点，但可以有原图的割点（此时在这个点双中就是普通的点），极大图，一个点双中可以有多个原图的割点
• 边双连通分量：其本身不存在割边，极大图
• 点双不具有传递性，边双具有传递性((x,y),(y,z)=>(x,z))

Tarjan

•  时间戳dfn：访问到的时间
• 返祖边：搜索树上连向其祖先节点的边
• 由于搜索树结构，不存在横向边（连向同层节点的边）
• low[u]定义：u和以u为根的子树通过返祖边（包括树边和非树边）能连到的最小的dfn
• 若是一条树边：low[u]=min(low[v[,low[u])
• 若是一条非树边：low[u]=min(low[u],dfn[v])

求割点

• 割点满足：其儿子的low[v]>=dfn[u]，即没有儿子跨过u，儿子与u相连只有树边
• 对于根要判断儿子个数大于1
• 可以走反向边
• 特判为根且搜索树上只有一个儿子，此时注意重边
• 求a,b间的割点，tarjan(a)判断如下

  if(low[v]>=dfn[x]){     if(x!=a&&x!=b&&dfn[x]<=low[b])ge[x]=true; }

求点双

•  每次访问到一个点将其入栈
• 若满足low[v]>=dfn[u]，则出栈直到v出，此时出栈的所有点和v是一个点双
• 每个点双，每个点都在一个环上，若点双有奇环，则所有点都在奇环
• 判奇环，二分图黑白染色

求割边

• 割边满足： 一条边只走一次，v没有另一条边到达u（父亲）即low[v]>dfn[u]
• 可以避免重边

 求边双

• 一边只走一次，若low[u]==dfn[u]（除了树边，没有其他到树上祖先的边），则为边双

点双缩点连图

• 割点单独为一个点，每个点双除割点，缩成一个点
• 割点向其所在的点双连边

边双缩点连图

• 每个边双缩点，用桥相连 

缩点连图

• 转为无向无环图 

有向图

• 强连通：图中存在路径u--->v和v--->u
• 弱连通：图中只存在路径u--->v或v--->u
• 强连通分量：该子图中对于任意一点对，存在路径u--->v和v--->u，极大图

Tarjan

• 时间戳dfn
• low[u]为u和以u为根的子树中能连到的还未出栈的最小dfn
• 访问到则入栈
• dfn[u]=low[u]，即到该点往上不会有强连通（有向边），
• 出栈直到u出栈，此时出栈的点为一个强连通分量

 强连通缩点

• 将有向图，转为有向无环图
• 之后可以考虑入度出度，topu排序dp
• 注意会有重边，所以缩点连边时要判断是否已经连上，不要重复计算入度出度
• 求加入最少的边变成一个强连通，先缩点

  int a=0,b=0; for(int i=1;i<=cc;++i){     if(!in[i])a++;     if(!out[i])b++; } if(cc==1)std::cout<<0< 

代码

• 割点

      auto tarjan=[&](auto &&tarjan,int x)->void{         dfn[x]=low[x]=++tt;int ch=0;         for(auto v:G[x]){             if(!dfn[v]){                 tarjan(tarjan,v);                 low[x]=min(low[x],low[v]);                 if(low[v]>=dfn[x]){                     ch++;                     if(x1!=rt||ch>1)                         ge[x]=true;                 }             }else low[x]=min(low[x],dfn[v]);         }         if(rt==x&&ch==1)ge[x]=false;     };

• 点双，缩点

          std::vector dfn(n+5,0),low(n+5,0);int tt=0;         std::vector sz(n+5,0),col(n+5,0);int cc=0;         std::stack st;std::vector> hs(n+5);         std::vector ge(n+5,false);int rt=0;         auto tarjan=[&](auto &&tarjan,int x)->void{             dfn[x]=low[x]=++tt;int ch=0;             st.push(x);             for(auto v:G[x]){                 if(!dfn[v]){                     tarjan(tarjan,v);                     low[x]=min(low[x],low[v]);                     if(low[v]>=dfn[x]){                         ch++;                         if(x!=rt||ch>1){                             ge[x]=true;                         }                         int y;cc++;//缩点                         do{                             y=st.top();st.pop();                             col[y]=cc;sz[cc]++;hs[cc].push_back(y);                         }while(y!=v);                         hs[cc].push_back(x);sz[cc]++;//割点放入                     }                 }else low[x]=min(low[x],dfn[v]);             }          };         for(int i=1;i<=n;++i)if(!dfn[i]){                 rt=i;                 tarjan(tarjan,i);             }

• 割边，边双，缩点

      std::vector dfn(n+5,0),low(n+5,0);int tt=0;     std::vector sz(n+5,0),col(n+5,0);int cc=0;     std::stack st;std::vector> hs(n+5);     auto tarjan=[&](auto &&tarjan,int x,int p)->void{         dfn[x]=low[x]=++tt;         st.push(x);         for(auto [v,i]:G[x]){//i为边的编号             if(i==p)continue;             if(!dfn[v]){                 tarjan(tarjan,v,i);                 low[x]=min(low[x],low[v]); //                if(low[v]>dfn[x]){ //                    std::cout<

• 强连通分量

      std::vector dfn(n+5,0),low(n+5);int tt=0;     std::stack st;std::vector> hs(n+5);     std::vector col(n+5,0),sz(n+5,0);int cc=0;     auto tarjan=[&](auto &&tarjan,int x)->void{         dfn[x]=low[x]=++tt;         st.push(x);         for(auto v:G[x]){             if(!dfn[v]){                 tarjan(tarjan,v);                 low[x]=min(low[x],low[v]);             }else if(!col[v])low[x]=min(low[x],dfn[v]);         }         if(dfn[x]==low[x]){             ++cc;             int y;             do{                 y=st.top();st.pop();                 col[y]=cc;sz[cc]++;hs[cc].push_back(y);             }while(y!=x);         }     };     for(int i=1;i<=n;++i){         if(!dfn[i])tarjan(tarjan,i);     }