Tarjan算法

2021-01-12

强连通分量

在这里插入图片描述

#include<bits/stdc++.h>

using namespace std;
const int MAXN=10010;
int dfn[MAXN],low[MAXN],Stack[MAXN];
vector<int> graph[MAXN];
//遍历深度以及栈顶指针(指向最后一个元素)
int deep=0,top=-1;
//标记元素是否在栈中
int tag[MAXN];
//强连通分量个数
int cnt=0;
//为不同的强连通分量上色区分
int color[MAXN];

void tarjan(int u){
    dfn[u]=low[u]=++deep;
    Stack[++top]=u;
    tag[u]=1;
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];

        //if(v==fa) continue;统计强连通分量个数不需要这个

        if(dfn[v]==0){

            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        //在栈中才进行更新
        else if(tag[v]==1){
            low[u]=min(low[u],dfn[v]);
        }

    }
    //cout<<u<<":"<<dfn[u]<<" "<<low[u]<<endl;
    //已经出现了一个强连通分量
    if(dfn[u]==low[u]){
        cnt++;
        //将同一个连通分量中的结点全部出栈
        while(tag[u]==1){
            tag[Stack[top]]=0;//置标记
            color[Stack[top]]=cnt;
            top--;
        }
    }
}


int main(){
    int n,m;
    cin>>n>>m;
    memset(dfn,0,sizeof(dfn));
    memset(tag,0,sizeof(tag));
    fill(low,low+n+1,INT_MAX);
    for(int i=0;i<m;i++){
        int from,to;
        cin>>from>>to;
        graph[from].push_back(to);
    }
    tarjan(1);
    cout<<cnt<<endl;
    for(int i=1;i<=n;i++){
        cout<<i<<" color "<<color[i]<<endl;
    }
}
//测试用例
/*
6 8
1 2
1 3
2 4
3 4
3 5
4 1
4 6
5 6
*/



*/

割点

在这里插入图片描述

思路一：依次删除每个割点，然后DFS
思路二：Tarjan算法

#include<bits/stdc++.h>

using namespace std;
const int MAXN=10010;
int deep=0,child=0,root=1,cnt=0;
vector<int> graph[MAXN];
int dfn[MAXN],low[MAXN],tag[MAXN];
vector<int> ans;
/*
访问过
  当前是根结点
  当前不是根结点 且 通过儿子能访问到更早访问过的结点

没访问过且此边不指向父亲节点
*/

//low找到更早的结点一定是不能违背dfs的遍历顺序的
//比如你已经访问过的一条边肯定是不能逆向访问的

//fa为当前结点的父节点
void tarjan(int u,int fa){

    dfn[u]=low[u]=++deep;
    for(int i=0;i<graph[u].size();i++){
        int v=graph[u][i];
        if(v==fa) continue;
        if(dfn[v]==0){//没有遍历过
            tarjan(v,u);
            low[u]=min(low[u],low[v]);//转换1
            //对于根结点是否为割点的判定，记录子树个数
            if(u==root) child++;
            //其他结点u若符合该条件，u就是割点
            //这里改为low[v]>dfn[u] ,则(u,v)是一条割边
            else if(dfn[u]<=low[v]){//理解:不能访问到比自己更先遍历的结点,等于则是刚好成环的那种情况
                tag[u]=1;
            }
        }
        else if{//遍历过且不是指向父亲
            low[u]=min(low[u],dfn[v]);
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    memset(dfn,0,sizeof(dfn));
    fill(low,low+n,INT_MAX);
    memset(tag,0,sizeof(tag));
    for(int i=0;i<m;i++){
        int from,to;
        cin>>from>>to;
        graph[from].push_back(to);
        graph[to].push_back(from);
    }
    tarjan(root,0);
    if(child>=2) tag[root]=1;

    for(int i=0;i<n;i++){
        if(tag[i]){
            cnt++; ans.push_back(i);
        }
    }
    cout<<cnt<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}