连通分量与Tarjian

所以Tarjian到底怎么读

强连通分量

• 基本概念
  • 强连通 如果两个顶点可以相互通达，则称两个顶点强连通
    
  • 强连通图 如果有向图G的每两个顶点都强连通，称G是一个强连通图。
• Tarjian
  Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
• 定义
  • dfn[u]: 为节点u搜索的次序编号(时间戳)
  • low[u]: 为u或u的子树能够追溯到的最早的栈中节点的次序号。
• 判定
  • low[u]:=min(low[u],dfn[v])——(u,v)为后向边，v不是u的子树；
  • low[u]:=min(low[u],low[v])——(u,v)为树枝边，v为u的子树；
  • 当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

模板题：信息传递

题目描述

有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti同学。
游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息，但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入

输入共2行。
第1行包含1个正整数n表示n个人。 n ≤ 200000
第2行包含n个用空格隔开的正整数T1,T2,……,Tn,其中第i个整数Ti示编号为i的同学的信息传递对象是编号为Ti的同学，Ti≤n且Ti≠i。数据保证游戏一定会结束。

输出

输出共 1 行，包含 1 个整数，表示游戏一共可以进行多少轮。

样例输入

5
2 4 2 3 1

样例输出

3

提示

游戏的流程如图所示。当进行完第 3 轮游戏后，4 号玩家会听到 2 号玩家告诉他自
己的生日，所以答案为 3。当然，第 3 轮游戏后，2 号玩家、3 号玩家都能从自己的消息
来源得知自己的生日，同样符合游戏结束的条件。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define met(a,x) memset(a,x,sizefo(a))
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+10;
int n,tol,dep;
int head[maxn],low[maxn],dfn[maxn],ans=maxn;
bool vis[maxn];
stack<int>st;
struct edge
{
    int v,next;
}e[maxn];
void addedge(int u,int v)
{
    e[++tol].next=head[u];
    e[tol].v=v;
    head[u]=tol;
}
void tarjian(int u)
{
    dfn[u]=low[u]=++dep;
    st.push(u);
    vis[u]=true;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(!dfn[v]){
            tarjian(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        int cnt=0;
        while(1){
            int now=st.top();
            st.pop();
            vis[u]=0;
            cnt++;
            if(now==u)break;
        }
        if(cnt>1) ans=min(ans,cnt);
    }
}
int main()
{
    scanf("%d",&n);
    int v;
    for(int i=1;i<=n;i++){
        scanf("%d",&v);
        addedge(i,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjian(i);
        }
    }
    printf("%d\n",ans);
    return 0;
}

求割点

• 基本概念：
  • 割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。
  • 若low[v]>=dfn[u],则u为割点。因low[v]>=dfn[u]，则说明v通过子孙无法到达u的祖先。那么对于原图，去掉u后，必然会分成两个子图。
• 模板

 /*
* 求无向图的割点和桥
 * 可以找出割点和桥，求删掉每个点后增加的连通块。
 * 需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重
 */
 const int MAXN = 10010;
 const int MAXM = 100010;
 struct Edge{
 int to,next;
 bool cut;//是否为桥的标记
 }edge[MAXM];
 int head[MAXN],tot;
 int Low[MAXN],DFN[MAXN],Stack[MAXN];
 int Index,top;
  bool Instack[MAXN];
  bool cut[MAXN];
  int add_block[MAXN];//删除一个点后增加的连通块
  int bridge;
  void addedge(int u,int v){
  edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false
;
  head[u] = tot++;
  }
  void Tarjan(int u,int pre){
  int v;
  Low[u] = DFN[u] = ++Index;
  Stack[top++] = u;
  Instack[u] = true;
  int son = 0;
  int pre_cnt = 0; //处理重边，如果不需要可以去掉
  for(int i = head[u];i != ?1;i = edge[i].next){
  v = edge[i].to;
  if(v == pre && pre_cnt == 0){pre_cnt++;continue;}
  if( !DFN[v] ){
  son++;
  Tarjan(v,u);
  if(Low[u] > Low[v])Low[u] = Low[v];
  //桥
  //一条无向边(u,v) 是桥，当且仅当(u,v) 为树枝边，且满足
DFS(u)<Low(v)。
  if(Low[v] > DFN[u]){
  bridge++;
  edge[i].cut = true;
  edge[i^1].cut = true;
  }
  //割点
  //一个顶点u 是割点，当且仅当满足(1) 或(2) (1) u 为树根，且u 有多于一个子树。
  //(2) u 不为树根，且满足存在(u,v) 为树枝边(或称父子边，
  //即u 为v 在搜索树中的父亲)，使得DFS(u)<=Low(v)
  if(u != pre && Low[v] >= DFN[u]){//不是树根
  cut[u] = true;
  add_block[u]++;
    }
  }
  else if( Low[u] > DFN[v])
  Low[u] = DFN[v];
  }
  //树根，分支数大于1
  if(u == pre && son > 1)cut[u] = true;
  if(u == pre)add_block[u] = son ? 1;
  Instack[u] = false;
  top??;
  }

【学习笔记】连通分量与Tarjian

原文：https://www.cnblogs.com/smallocean/p/9576467.html