Strongly connected component

Connected component ： Any two points can reach each other .（ notes ： Any point itself is strongly connected ）
Strong connected components ： Maximal connected component , After adding any point, it is not a connected component
Directed acyclic graph （DAG）： That is, topology .

dfs order ： according to dfs Number each point in the order of
Beside the branches ：(x,y),x yes y Parent node
Forward edge ：(x,y),x yes y The ancestor node of
Back to the side ：(x,y),y yes x The ancestor node of
Cross edge ：(x,y), One of them has been searched
It's usually on the left , The one on the right is not called cross edge
Judge whether a point is in the strongly connected component ：
①： Is it possible to return to the ancestor node , That is, there is a backward edge pointing to the ancestor node
②： Go to a horizontal fork first , Then go to the ancestor node
Tarjan Algorithm for strong connected components ：
Time stamp ： adopt dfs Set a number for each point .
Define two timestamps for each point ：
dfn[u] Means to traverse to u Time for
low[u] From u Start walking , The smallest timestamp that can be traversed .
If u Is the highest point of the strongly connected component , be dfn[u]=low[u]

tarjan Algorithm ： encounter dfn[u]==low[u] Is the strongly connected component , This means that when the smallest point he can reach is itself, it is a strongly connected component . Because strongly connected components , It must be that every two points can reach each other . So it is bound to form a ring , Because we are dfs It must be from top to bottom, that is, the timestamp is also from small to large , So we think the smallest point on this ring is the key point . Because in the specific traversal process, it must be after each point traversal is completed to judge whether it conforms to strongly connected variables , When judging in this way, the variable that cannot be reached has been out of the stack , What can be reached is still in the stack , And is the largest （ This point has been traversed ）. In this way, all points including itself are put out of the stack , Form a strongly connected component .

Shrinkage point ： Because the connected components can reach each other , That is, after reaching this connected component through the outer point, you can reach any point in the connected component , Therefore, this connected component can be reduced to a point , After shrinking the point, the whole graph will be called a directed acyclic graph .

tarjan Algorithm code template ：

void tarjan(int u)
{
    
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
    
        int j=e[i];
        if(!dfn[j])
        {
    
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
    
        ++scc_cnt;// The number of connected components plus 1
        int y;
        do
        {
    
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;//y In this connected component 
            Size[scc_cnt]++;
        }while(y!=u);
    }
}

Shrink point template ：

for(int i=1;i<=n;i++)
    {
    
        for(int j=h[i];~j;j=ne[j])
        {
    
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) dout[a]++;//a The output plus 1, That is, he came here connected , But after finding the connected component, it is not connected , They should be connected 
        }
    }

Topic link
kosaraju Algorithm （ two dfs）： Positive direction can reach , What can also be reached in the reverse direction is the strongly connected component , Here is the first time dfs The order of stacking is in the order of traversal , So the first traversal must be the last stack , So after the node enters the stack completely , From the top of the stack to the bottom of the stack is actually in accordance with dfs Sequential execution .

Algorithm template ：

void dfs1(int u)
{
    
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
    
        int j = e[i];
        if (!st[j])
            dfs1(j);
    }
    stk[ ++ top] = u;
}
void dfs2(int u)
{
    
    id[u] = scc_cnt;
    sz[scc_cnt] ++ ;
    st[u] = true;
    for (int i = hs[u]; ~i; i = ne[i])
    {
    
        int j = e[i];
        if (!st[j])
            dfs2(j);
    }
}

Here is an example ：
Topic link