20-2-28-kosarajuアルゴリズム-

Ksaraju

以下のコードはkuangbinのテンプレートから来ます.

/*
*Kosaraju  ,      O(n+m)
*     Tarjan          ,      
*           ,       
*/
const int MAXN=20010;
const int MAXM=50010;
struct Edge{
    int to,next;
}edge1[MAXM],edge2[MAXM];
//edge1   G, edge2   GT
int tot1,tot2;

int head1[MAXN],head2[MAXN];
//mark1 mark2  head1 head2       DFS   
bool mark1[MAXN],mark2[MAXN];

int st[MAXN];
int cnt1;
//st[i]       i       st[i]
    //     dfs,            

int Belong[MAXN];//               
int cnt2;//cnt2           
int num;//    ,              
int setNum[MAXN];//          ,  0~cnt2-1
void addedge(int u, int v){
    edge1[tot1].to=v;
    edge1[tot1].next=head1[u];
    head1[u]=tot1++;

    edge2[tot2].to=u;
    edge2[tot2].next=head2[v];
    head2[v]=tot2++;
}

void DFS1(int u){
    mark1[u]=true;
    for(int i=head1[u];i!=-1;i=edge1[i].next){
        if(!mark1[edge1[i].to]){
            DFS1(edge1[i].to);
        }
    }
    st[cnt1++]=u;
}

//      DFS  ,  DFS           ,
    //       Belong[] cnt2
void DFS2(int u){
    mark2[u]=true;
    
    num++;//          1
    Belong[u]=cnt2;

    for(int i=head2[u];i!=-1;i=edge2[i].next){
        if(!mark2[edge2[i].to]){
            DFS2(edge2[i].to);
        }
    }
}

//     1  
void solve(int n){
    memset(mark1,false,sizeof(mark1));
    memset(mark2,false,sizeof(mark2));
    cnt1=cnt2=0;
    for(int i=1;i<=n;i++){
        if(!mark1[i]){
            DFS1(i);
        }
    }
    //           DFS  
    for(int i = cnt1−1;i >= 0; i−−)
        if(!mark2[st[i]]){
            num = 0;```
            DFS2(st[i]);
            setNum[cnt2++] = num;
        }
}

上のテンプレートを見終わったら、なぜこのようにすればいいですか?

原因はここで

を見つけることができます.

上のブログには、このような可能性のある理由が重要なところで述べられています.ここで抜粋します.
強い連結成分を小さくしてDAGを得ることができます.このとき、符号が一番大きいノードは、DAGヘッダ(ツリーのルートを検索する)の強い連結成分に属することが分かる.したがって、サイドを逆にすると、この強い連結成分以外の頂点に沿ってアクセスできません.強い連結成分内の他の頂点については、その到達性は逆方向の影響を受けないので、第二のDFSの時には、強い連結成分の中のすべての頂点を遍歴することができる.——————————————————————————————————————————————————————————————————————————————————————————————————————著作権声明:本文はCSDNブロガー「肘zhouszi」のオリジナル文章で、CC 4.0 BY-SA著作権契約に従い、転載は原文の出所リンクと本声明を添付してください.原文のリンク:https://blog.csdn.net/zhouzi2018/article/details/81610804