Nowcoder-Graph-Class-Problems

¶连通性

¶无向图割、桥、双连通分量

割点:删去该点及其边，图不再连通
割边(桥):删去该边，图不再连通
一个图不存在割点->点双连通图
一个图的极大点双连通子图是它的点双连通分量
一个图不存在割边->边双连通图
一个图的极大边双连通子图是它的边双连通分量

$Tarjan$ 求割点和桥
时间戳$dfn$:第几个搜到这个点
返祖边:搜索书上一个点连向其祖先节点的边
(横向边:搜索树上一个点连向它另一条支链上的点的边–无向图中不存在)
追溯值$low$:当前点及其子树通过一条返祖边能连到的dfn最小的点
如果$<u,v>$ 是搜索树的边:$low[u]=min(low[u],low[v])$。
如果$<u,v>$ 是返祖边:$low[u]=min(low[u],dfn[v])$。

int head[N],edge[M],nxt[M];
int dfn[N],low[N];
bool cot_cpt[N],bridge[M];
int idx=0,cnt=0,root=0,cnt_bridge=0,cnt_cot_cpt=0;

void add(int a,int b){
    edge[idx]=b,nxt[idx]=head[a],head[a]=idx++;
}

void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    int flag=0;
    for(int i=head[u];i!=-1;i=nxt[i]){
        int v=edge[i];
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){                      //求割边
                bridge[i]=true;
                cnt_bridge++;
            }
            if(low[v]>=dfn[u]){                     //求割点
                flag++;
                if(!cot_cpt[u]&&(v!=root||flag>1)){
                    cot_cpt[u]=true;
                    cnt_cot_cpt++;
                }
            }
        }else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
}