Strong connected component of "tarjan" undirected graph

Learning resources

• https://www.bilibili.com/video/BV1Q7411e7bM?spm_id_from=333.337.search-card.all.click
• Code implementation -- Advanced algorithm guide $lyd$

Conclusion ( The laws of )

1. Cut point decision rule
Judgment point $x$ Whether it is a cut point , The corresponding edge is $x\to y$

1. if $x$ Not root node ,$low[y]>=dfn[x]$, be $x$ For the cut point
2. if $x$ Root node , There are at least two points $y$ bring $low[y]>=dfn[x]$, be $x$ For the cut point

2. Bridge decision rule
For edge $x\to y$, if $low[y]>dfn[x]$ Then the side $x\to y$ For the bridge
3. Add... To an undirected graph $(cnt+1)/2$ An edge can become an edge biconnected graph ( The degree after shrinking point is $1$ The number of points $cnt$)

Template

//  Seeking Bridge 
int n,m;
struct node{
    
    int to,ne;
}e[10005 << 1];
int idx = 1;
int h[10005];
int dfn[10005],low[10005],ecc;
int id[10005],tim;
int stk[10005], ins[10005],top;
int sz[10005];
bool isb[10005];


void add(int u,int v){
    
    e[++idx] = {
    v,h[u]};
    h[u] = idx;
}

//  Record the number of the side where the current point is located 
void tarjan(int u,int fa){
    
    dfn[u] = low[u] = ++tim;
    stk[++top] = u;
    for(int i = h[u];i;i=e[i].ne){
    
        int v = e[i].to;
        if(!dfn[v]){
    
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]){
    
                isb[i] = isb[i^1] = 1;
            }
        }
        else if(i != (fa^1)) low[u] = min(low[u],low[v]);
    }
    if(low[u] == dfn[u]){
    
        ecc++;int y;
        do{
    
            y = stk[top--];
            id[y] = ecc;
        }while(y!=u);
    } 
}
signed main()
{
    
    cin>>n>>m;
    while(m--){
    
        int u,v;
        cin>>u>>v;
        if(u == v) continue; //  Remove self ring 
        add(u,v);add(v,u);
    }
    tarjan(1,-1);
    return 0;
}

//  Please cut point 
struct node{
    
    int to,ne;
}e[1005<<1];
int h[1005];
int idx = 1;
void add(int u,int v){
    
    e[++idx] = {
    v,h[u]};
    h[u] = idx;
}
int n;
//  Find the point connected component 
int dfn[1005],low[1005],dcc,tim;
int stk[1005],top;
bool cut[1005];
vector<int> v[1005];
int root;

//  seek vdcc Templates 
void tarjan(int x){
    
    dfn[x] = low[x] = ++tim;
    stk[++top] = x;
    if(x == root && !h[x]){
    
        dcc++;
        v[dcc].push_back(x);
        return;
    }
    int f = 0;
    for(int i = h[x];i;i=e[i].ne){
    
        int j = e[i].to;
        if(!dfn[j]){
    
            tarjan(j);
            low[x] = min(low[x],low[j]);
            if(low[j] >= dfn[x]){
    
                f++;
                if(x != root || f>1 ) cut[x] = 1;
                dcc++;
                int y;
                do{
    
                    y = stk[top--];
                    v[dcc].push_back(y);
                }while(y!=j);
                v[dcc].push_back(x);
            }
        }
        else low[x] = min(low[x],dfn[j]);
    }
}

signed main()
{
    
		while(m--){
    
	        int u,v;
	        cin>>u>>v;
	        if(u == v) continue; //  Remove self ring 
	        add(u,v);add(v,u);
	    }
        //  seek  vdcc
        // When finding the cut point root Nodes are very important , The conditions used to judge the cut point 
        for(root = 1;root <= k;root++){
    
            if(!dfn[root]) tarjan(root);
        }
    return 0;
}

practice

10098. 「 A passbook 3.6 example 1」 The path of separation

. Add... To an undirected graph $(cnt+1)/2$ An edge can become an edge biconnected graph

int n,m;
struct node{
    
    int to,ne;
}e[10005 << 1];
int idx = 1;
int h[10005];
int dfn[10005],low[10005],ecc;
int id[10005],tim;
int stk[10005], ins[10005],top;
int sz[10005];
bool isb[10005];
void add(int u,int v){
    
    e[++idx] = {
    v,h[u]};
    h[u] = idx;
}
void tarjan(int u,int fa){
    
    dfn[u] = low[u] = ++tim;
    stk[++top] = u;
    for(int i = h[u];i;i=e[i].ne){
    
        int v = e[i].to;
        if(!dfn[v]){
    
            tarjan(v,i);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]){
    
                isb[i] = isb[i^1] = 1;
            }
        }
        else if(i != (fa^1)) low[u] = min(low[u],low[v]);
    }
    if(low[u] == dfn[u]){
    
        ecc++;int y;
        do{
    
            y = stk[top--];
            id[y] = ecc;
        }while(y!=u);
    } 
}
int d[10005];
signed main()
{
    
    cin>>n>>m;
    while(m--){
    
        int u,v;
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    tarjan(1,-1);
    forr(i,2,idx){
    
        if(isb[i]) d[id[e[i].to]]++;
    }
    int cnt = 0;
    forr(i,1,ecc) if(d[i] == 1) cnt++;
    cout << (cnt+1)/2 << endl;
    return 0;
}

10099. 「 A passbook 3.6 example 2」 Mine construction

Undirected graph , It is hoped that when an accident occurs at the construction site, all the workers at the coal mining point can have a way out and escape to the rescue exit . No matter which coal mining site collapses , Workers at other coal mining sites have a road leading to the rescue exit .
At least several rescue exits need to be set up , And the setting scheme of different minimum rescue exits .

For the code of statistical scheme method, see

int t;
struct node{
    
    int to,ne;
}e[1005<<1];
int h[1005];
int idx = 1;
void add(int u,int v){
    
    e[++idx] = {
    v,h[u]};
    h[u] = idx;
}
int n;
//  Find the point connected component 

int dfn[1005],low[1005],dcc,tim;
int stk[1005],top;
bool cut[1005];
vector<int> v[1005];
int root;



//  seek vdcc Templates 
void tarjan(int x){
    
    dfn[x] = low[x] = ++tim;
    stk[++top] = x;

    //  Find the isolation point 
    //  According to the following code , seek cc Need a son , Special judgment is needed here ;
    if(x == root && !h[x]){
    
        dcc++;
        v[dcc].push_back(x);
        return;
    }
    int f = 0;
    for(int i = h[x];i;i=e[i].ne){
    
        int j = e[i].to;
        if(!dfn[j]){
    
            tarjan(j);
            low[x] = min(low[x],low[j]);
            if(low[j] >= dfn[x]){
    
                f++;
                if(x != root || f>1 ) cut[x] = 1;
                dcc++;
                int y;
                do{
    
                    y = stk[top--];
                    v[dcc].push_back(y);
                }while(y!=j);
                v[dcc].push_back(x);
            }
        }
        else low[x] = min(low[x],dfn[j]);
    }
}



signed main()
{
    
    while(cin>>n,n){
    
        forr(i,1,dcc) v[i].clear();
        top = 0;idx = 1,tim=0;
        dcc = 0;
        root = 0;
        mem(dfn,0);mem(low,0);
        mem(h,0);mem(cut,0);
        int k;
        while(n--){
    
            int u,v;cin>>u>>v;
            root = max({
    root,u,v});
            add(u,v);add(v,u);
        }

        k = root;
        //  seek  vdcc
        
        for(root = 1;root <= k;root++){
    
            if(!dfn[root]) tarjan(root);
        }

        int res = 0;
        int ans = 1;
        forr(i,1,dcc){
    
            
            int cnt = 0;
            for(auto j:v[i]){
    
                if(cut[j]) cnt++;
            }

            if(!cnt) 
                if(v[i].size()) res+=2,ans *= (v[i].size()*(v[i].size()-1))/2;
                else res++;
            else if(cnt == 1) res++, ans *= (v[i].size()-1);

        }
        printf("Case %llu: %llu %llu\n",++t,res,ans);
        
    }
    return 0;
}

10101. 「 A passbook 3.6 practice 2」 Sniffer

Give me two points $a,b$ Ask if there is a cut point that makes $a,b$ Not in a connected component
Cut some board questions Add one more condition when judging the cutting point For edge $x\to y$ bring $low[y]>=low[x]\&\&dfn[y]<=dfn[b]$

struct node {
    
    int to, ne;
} e[200005 << 1];
int h[200005];
int idx = 1;
void add(int u, int v) {
    
    e[++idx] = {
    v, h[u]};
    h[u] = idx;
}
int n;
//  Find the point connected component 

int dfn[200005], low[200005], dcc, tim;
int stk[200005], top;
bool cut[200005];
vector<int> v[200005];
vector<int> id[200005];
int d1, d2;

//  seek vdcc Templates 
void tarjan(int x) {
    
    dfn[x] = low[x] = ++tim;
    stk[++top] = x;
    int f = 0;

    for (int i = h[x]; i; i = e[i].ne) {
    
        int j = e[i].to;

        if (!dfn[j]) {
    
            tarjan(j);
            low[x] = min(low[x], low[j]);

            if (low[j] >= dfn[x]) {
    
                f++;

                if (x != d1 || f > 1)
                    if (dfn[d2] >= dfn[j])
                        cut[x] = 1;
            }
        } else
            low[x] = min(low[x], dfn[j]);
    }
}


int main() {
    
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    cin >> n;
    int x, y;

    while (cin >> x >> y, x || y) {
    
        add(x, y);
        add(y, x);
    }

    cin >> d1 >> d2;
    tarjan(d1);

    forr(i, 1, n) {
    
        if (cut[i]) {
    
            cout << i << endl;
            return 0;
        }
    }
    puts("No solution");
    return 0;
}

10103. 「 A passbook 3.6 practice 4」 Electric power

For a point $x$
If exist $cnt$ Child nodes ( In the search tree ), if x Contribute to the root node $cnt$ , otherwise $cnt+1$ Enumerating points for maximum contribution

struct node {
    
    int to, ne;
} e[200005 << 1];
int h[200005];
int idx = 1;
void add(int u, int v) {
    
    e[++idx] = {
    v, h[u]};
    h[u] = idx;
}
int n;
//  Find the point connected component 
int dfn[200005], low[200005], dcc, tim;
int stk[200005], top;
bool cut[200005];
vector<int> v[200005];
vector<int> id[200005];
int d1, d2;
//  seek vdcc Templates 
void tarjan(int x) {
    
    dfn[x] = low[x] = ++tim;
    stk[++top] = x;
    int f = 0;

    for (int i = h[x]; i; i = e[i].ne) {
    
        int j = e[i].to;

        if (!dfn[j]) {
    
            tarjan(j);
            low[x] = min(low[x], low[j]);

            if (low[j] >= dfn[x]) {
    
                f++;

                if (x != d1 || f > 1)
                    if (dfn[d2] >= dfn[j])
                        cut[x] = 1;
            }
        } else
            low[x] = min(low[x], dfn[j]);
    }
}
int main() {
    
    cin >> n;
    int x, y;
    while (cin >> x >> y, x || y) {
    
        add(x, y);
        add(y, x);
    }
    cin >> d1 >> d2;
    tarjan(d1);
    forr(i, 1, n) {
    
        if (cut[i]) {
    
            cout << i << endl;
            return 0;
        }
    }
    puts("No solution");
    return 0;
}

10104. 「 A passbook 3.6 practice 5」Blockade

Similar to the above question

typedef long long ll;
int pri[16] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
const int inf = 0x3f3f3f3f;
const int INF = ~0ULL;
const int N = 1e6+10;
int n,m;
vector<int> g[100005];
int dfn[100005],low[100005];
int tim;
int ans[100005];
int sz[100005];
bool cut[100005];

void tarjan(int x){
    
    dfn[x] = low[x] = ++tim,sz[x] = 1;
    int f = 0,sum = 0;
    for(auto v:g[x]){
    
        if(!dfn[v]){
    
            tarjan(v);
            sz[x] += sz[v];
            low[x] = min(low[x],low[v]);
            if(low[v] >= dfn[x]){
    
                f++;
                ans[x] += sz[v]*(n-sz[v]);
                sum += sz[v];
                if(x!=1 || f > 1) cut[x] = 1;
            }
        }
        else low[x] = min(low[x],dfn[v]);
    }
    if(cut[x]) ans[x] += (n-1-sum)*(sum+1)+n-1;
    else ans[x] = 2*(n-1);
}


signed main()
{
    
    cin>>n>>m;
    while(m--){
    
        int u,v;
        cin>>u>>v;
        if(u==v) continue;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    tarjan(1);

    forr(i,1,n) cout << ans[i] << endl;

    return 0;
}