精华内容
下载资源
问答
  • 迷宫城堡为了训练小希方向感,Gardon建立了一座大城堡,里面N个房间(N)和M条通道(M),每个通道都是单向,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以...

    迷宫城堡

    Problem Description
    为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000),每个通道都是单向的,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的,即:对于任意的i和j,至少存在一条路径可以从房间i到房间j,也存在一条路径可以从房间j到房间i。
     

    Input
    输入包含多组数据,输入的第一行有两个数:N和M,接下来的M行每行有两个数a和b,表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
     

    Output
    对于输入的每组数据,如果任意两个房间都是相互连接的,输出"Yes",否则输出"No"。
     

    Sample Input
    3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0
     

    Sample Output
    Yes No
     


    解题思路

    有向图连通分量模板题



    代码

    #include <iostream>
    #include <cstdio>
    #include <map>
    #include <cmath>
    #include <string.h>
    #include <algorithm>
    #include <set>
    #include <sstream>
    #include <vector>
    #include <queue>
    #include <stack>
    using namespace std;
    
    const int maxn = 10000+10;
    const int INF = 0x3f3f3f3f;
    
    
    vector<int> G[maxn];
    int pre[maxn];///第一次进入dfs时的层数
    int lowlink[maxn];///能追溯到的dfs层数最小(最先被发现)的根祖先的 pre 值
    int sccno[maxn];///当前点属于第几个连通分量
    int dfsLock;///dfs层数
    int sccCnt;///连通分量个数
    
    stack<int> s;
    
    int n,m;
    
    
    void dfs(int u){
        ///一开始并不知道这个点的根祖是谁,也不知道跟祖先最先在第几层进入dfs
        pre[u] = lowlink[u] = ++dfsLock;
    
        s.push(u);
        ///遍历这个点能到达的点
        for(int i = 0;i<G[u].size(); ++i){
            int v = G[u][i];
            if(!pre[v]){///这个点没有进入过dfs
                dfs(v);
                ///是否通过v点找到了u点的祖先,如果是,更新u点的最小层数
                lowlink[u] = min(lowlink[u],lowlink[v]);
            }
            ///如果这个点已经进入过dfs了,但是还没确定是属于哪个连通分支的点
            ///这个点可能是u点的祖先
            else if(!sccno[v]){
                lowlink[u] = min(lowlink[u],pre[v]);///*****这里书上写的是pre 个人觉得写lowlink是一样的,不知道对不对****
            }
        }
    
        ///如果他下面的点都没有改变他的最小值,说明他是一个根祖先,也就是一个连通分支的入口
        if(lowlink[u] == pre[u]){
            sccCnt++;
    
            while(1){
                int x = s.top(); s.pop();
                sccno[x] = sccCnt;
                if(x == u) break;
            }
        }
    
    }
    
    
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF){
            if(m==0 && n==0) break;
    
            ///初始化
            for(int i =0; i<maxn; ++i) G[i].clear();
            while(!s.empty()) s.pop();
            memset(pre,0,sizeof(pre));
            memset(lowlink,0,sizeof(lowlink));
            memset(sccno,0,sizeof(sccno));
            dfsLock = sccCnt = 0;
    
            int u,v;
            for(int i = 0;i<m;++i){
                scanf("%d%d",&u,&v);
                G[u-1].push_back(v-1);
            }
            for(int i = 0; i<n; ++i){
                if(!pre[i]) dfs(i);
            }
            if(sccCnt==1) printf("Yes\n");
            else printf("No\n");
        }
    
    
        return 0;
    }
    

    展开全文
  •   #include&lt;cstdio&gt; #include&lt;cstring&...#define maxn 500//图的规模 using namespace std; vector&lt;int&gt; G[maxn];//邻接表存图 int pre[maxn], l...

     

    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<stack>
    #define maxn 500//图的规模
    using namespace std;
    
    vector<int> G[maxn];//邻接表存图
    int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
    stack<int> S;
    
    void dfs(int u){
           pre[u] = lowlink[u] = ++dfs_clock;
           S.push(u);
           for(int i=0; i < G[u].size(); i++){
                  int v = G[u][i];
                  if(!pre[v]){
                         dfs(v);
                         lowlink[u] = min(lowlink[u], lowlink[v]);
                  }else if(!sccno[v]) {
                         lowlink[u] = min(lowlink[u], pre[v]);
                  }
           }
           if(lowlink[u] == pre[u]) {
                  scc_cnt ++ ;
                  for(;;) {
                         int  x = S.top(); S.pop();
                         sccno[x] = scc_cnt;
                         if(x == u) break;
                  }
           }
    }
    
    void find_scc(int n){
           dfs_clock = scc_cnt = 0;
           memset(sccno, 0, sizeof(sccno));
           memset(pre, 0, sizeof(pre));
           for(int i = 0; i < n; i++)
                  if(!pre[i]) dfs(i);
    }
    int main()
    {
           int T,i;
           scanf("%d",&T);
           while(T--)
           {
                  int n,m;
                  scanf("%d%d",&n,&m);
                  for(i=0;i<m;i++)
                  {
                         int a,b;
                         scanf("%d%d",&a,&b);
                         G[a].push_back(b);
                  }
                  find_scc(n);
                  for(i=0;i<n;i++)
                  {
                         printf("%d ",sccno[i]);
                  }
                  printf("\n");
           }
    	return 0;
    }
    

     

         图用 邻接表存储

    sccno[i]表示  i所在的连通分量数
    scc_cnt       表示一共的连通分量数

     

     

     

     

     

    展开全文
  • 如何求有向图的极大强连通分量? --------------------------------------------------------------- 利用深度优先搜索,求有向图G的强连通分支的算法步骤: 1)对G进行深度优先搜索并按递归调用完成的先后...

    题目描述

        We get lost again , we can not find our friends...But luckly , we have mobile phone.They are moving by group,and we know our friend in the same group can connect with each other in directly or indirectly ways .So you must tell me the min number of our friend's group. 

    输入描述

        First line is a interger T(<=200) , then T cases follow.
    A interger N(<=500) begin , as the number of my friends.
    Then A integer M, as M lines follow.
    Each line has two interger A,B , as A can connect B , but it doesn't mean B can connect A.
    Note index from 1.

    输出描述

     Tell me the min number of our friend's group. 

    样例输入

    1
    5 5
    1 2
    2 1
    2 3
    3 4
    4 1

    样例输出

    2
    

    如何求有向图的极大强连通分量?
    ---------------------------------------------------------------

    利用深度优先搜索,求有向图G的强连通分支的算法步骤:
    1)对G进行深度优先搜索并按递归调用完成的先后顺序对各顶点编号;
    2)改变G的每条边的方向,构造出新的有向图Gr
    3)按1)中的确定的顶点编号,从编号最大的顶点开始对Gr进行深度优先搜索。如果搜索的过程中没有访问遍Gr的所有顶点,则从未被访问过的顶点中选取编号最大的顶点,并从此顶点开始继续做深度优先搜索;
    4)在最后得到的Gr的深度优先生成森林中,每棵树上的顶点组成G的一个强连通分支

     

    求有向图的强联通分量(以下内容转载自http://blog.csdn.net/crfoxzl/archive/2009/04/15/4076414.aspx

     

    最关键通用部分:强连通分量一定是图的深搜树的一个子树。

     

    一、     Kosaraju算法

    1.      算法思路

    基本思路:

    这个算法可以说是最容易理解,最通用的算法,其比较关键的部分是同时应用了原图G和反图GT。(步骤1)先用对原图G进行深搜形成森林(树),(步骤2)然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT),能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林,继续步骤2直到 没有顶点为止。

    改进思路:

    当然,基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时,可能深搜到其他树上去,这是不允许的,强连通分量只能存在单棵树中(由开篇第一句话可知)),我们当然不这么做,我们可以巧妙的选择第二深搜选择的树的顺序,使其不可能深搜到其他树上去。想象一下,如果步骤2是从森林里选择树,那么哪个树是不连通(对于GT来说)到其他树上的呢?就是最后遍历出来的树,它的根节点在步骤1的遍历中离开时间最晚,而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择,在第一次深搜遍历时,记录时间i离开的顶点j,即numb[i]=j。那么,我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。 

    隐藏性质:

       分析到这里,我们已经知道怎么求强连通分量了。但是,大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢?如果在看上述思路的时候,你的脑子在思考,相信你已经知道了!!!它就是:如果我们把求出来的每个强连通分量收缩成一个点,并且用求出每个强连通分量的顺序来标记收缩后的节点,那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢?首先,应该明确搜索后的图一定是有向无环图呢?废话,如果还有环,那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量,而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列,我们在改进分析的时候,不是先选的树不会连通到其他树上(对于反图GT来说),也就是后选的树没有连通到先选的树,也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗?这就是Kosaraju算法的一个隐藏性质。 

    2.      伪代码

    Kosaraju_Algorithm:

     step1:对原图G进行深度优先遍历,记录每个节点的离开时间。

     step2:选择具有最晚离开时间的顶点,对反图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量。

     step3:如果还有顶点没有删除,继续step2,否则算法结束。 

    3.      实现代码:

    #include <iostream>

    using namespace std;

     

    const int MAXN = 110;

     

    typedef int AdjTable[MAXN]; //邻接表类型

     

    int      n;

    bool     flag[MAXN]; //访问标志数组

    int      belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

    int      numb[MAXN]; //结束时间标记,其中numb[i]表示离开时间为i的顶点

    AdjTable adj[MAXN], radj[MAXN]; //邻接表,逆邻接表

     

    //用于第一次深搜,求得numb[1..n]的值

    void VisitOne(int cur, int &sig)

    {

     flag[cur] = true;

     

     for ( int i=1; i<=adj[cur][0]; ++i )

     {

         if ( false==flag[adj[cur][i]] )

         {

             VisitOne(adj[cur][i],sig);

         }

     }

     

     numb[++sig] = cur;

    }

     

    //用于第二次深搜,求得belg[1..n]的值

    void VisitTwo(int cur, int sig)

    {

     flag[cur] = true;

     belg[cur] = sig;

     

     for ( int i=1; i<=radj[cur][0]; ++i )

     {

         if ( false==flag[radj[cur][i]] )

         {

             VisitTwo(radj[cur][i],sig);

         }

     }

    }

     

    //Kosaraju算法,返回为强连通分量个数

    int Kosaraju_StronglyConnectedComponent()

    {

     int i, sig;

     

     //第一次深搜

     memset(flag+1,0,sizeof(bool)*n);

     for ( sig=0,i=1; i<=n; ++i )

     {

         if ( false==flag[i] )

         {

             VisitOne(i,sig);

         }

     }

     

     //第二次深搜

     memset(flag+1,0,sizeof(bool)*n);

     for ( sig=0,i=n; i>0; --i )

     {

         if ( false==flag[numb[i]] )

         {

             VisitTwo(numb[i],++sig);

         }

     }

     

     return sig;  

    }

     

    二、     Trajan算法

    1.      算法思路:

    这个算法思路不难理解,由开篇第一句话可知,任何一个强连通分量,必定是对原图的深度优先搜索树的子树。那么其实,我们只要确定每个强连通分量的子树的根,然后根据这些根从树的最低层开始,一个一个的拿出强连通分量即可。那么身下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。

    那么如何确定强连通分量的根,在这里我们维护两个数组,一个是indx[1..n],一个是mlik[1..n],其中indx[i]表示顶点i开始访问时间,mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样,在一次深搜的回溯过程中,如果发现mlik[i]==indx[i]那么,当前顶点就是一个强连通分量的根,为什么呢?因为如果它不是强连通分量的跟,那么它一定是属于另一个强连通分量,而且它的根是当前顶点的祖宗,那么存在包含当前顶点的到其祖宗的回路,可知mlik[i]一定被更改为一个比indx[i]更小的值。

    至于如何拿出强连通分量,这个其实很简单,如果当前节点为一个强连通分量的根,那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈,每次访问一个新节点,就压入堆栈。现在知道如何拿出了强连通分量了吧?是的,因为这个强连通分量时最先被压人堆栈的,那么当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗?假设在当前节点压入堆栈以后压入并且还存在,同时它不属于该强连通分量,那么它一定属于另一个强连通分量,但当前节点是它的根的祖宗,那么这个强连通分量应该在此之前已经被拿出。现在没有疑问了吧,那么算法介绍就完了。 

    2.      伪代码:

    Tarjan_Algorithm:

       step1:

       找一个没有被访问过的节点v,goto step2(v)。否则,算法结束。

          step2(v):

           初始化indx[v]和mlik[v]

           对于v所有的邻接顶点u:

                  1)     如果没有访问过,则step2(u),同时维护mlik[v]

                  2)     如果访问过,但没有删除,维护mlik[v]

           如果indx[v]==mlik[v],那么输出相应的强连通分量 

    3.      实现代码

    #include <iostream>

    using namespace std;

     

    const int MAXN    = 110;

    const char NOTVIS = 0x00;   //顶点没有访问过的状态

    const char VIS     = 0x01;   //顶点访问过,但没有删除的状态

    const char OVER    = 0x02;   //顶点删除的状态

     

    typedef int AdjTable[MAXN]; //邻接表类型

     

    int      n;

    char     flag[MAXN];         //用于标记顶点状态,状态有NOTVIS,VIS,OVER

    int      belg[MAXN];         //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

    int      stck[MAXN];         //堆栈,辅助作用

    int      mlik[MAXN];         //很关键,与其邻接但未删除顶点地最小访问时间

    int      indx[MAXN];         //顶点访问时间

    AdjTable adj[MAXN];          //邻接表

     

    //深搜过程,该算法的主体都在这里

    void Visit(int cur, int &sig, int &scc_num)

    {

       int i;

     

       stck[++stck[0]] = cur; flag[cur] = VIS;

       mlik[cur] = indx[cur] = ++sig;

     

       for ( i=1; i<=adj[cur][0]; ++i )

       {

          if ( NOTVIS==flag[adj[cur][i]] )

          {

              Visit(adj[cur][i],sig,scc_num);

              if ( mlik[cur]>mlik[adj[cur][i]] )

              {

                 mlik[cur] = mlik[adj[cur][i]];

              }

          }

          else if ( VIS==flag[adj[cur][i]] )

          {

              if ( mlik[cur]>indx[adj[cur][i]] ) //该部分的indx应该是mlik,但是根据算法的属性,使用indx也可以,且时间更少

              {

                 mlik[cur] = indx[adj[cur][i]]; 

              }

          }

       }

     

       if ( mlik[cur]==indx[cur] )

       {

          ++ scc_num;

          do

          {

              belg[stck[stck[0]]] = scc_num;

              flag[stck[stck[0]]] = OVER;

          }

          while ( stck[stck[0]--]!=cur );   

       }

    }

     

    //Tarjan算法,求解belg[1..n],且返回强连通分量个数,

    int Tarjan_StronglyConnectedComponent()

    {

       int i, sig, scc_num;

     

       memset(flag+1,NOTVIS,sizeof(char)*n);

     

       sig = 0; scc_num = 0; stck[0] = 0;

       for ( i=1; i<=n; ++i )

       {

          if ( NOTVIS==flag[i] )

          {

              Visit(i,sig,scc_num);

          }

       }

     

       return scc_num;

    } 

     

    三、   Gabow算法

    1.      思路分析

    这个算法其实就是Tarjan算法的变异体,我们观察一下,只是它用第二个堆栈来辅助求出强连通分量的根,而不是Tarjan算法里面的indx[]和mlik[]数组。那么,我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。

    我们使用类比方法,在Tarjan算法中,每次mlik[i]的修改都是由于环的出现(不然,mlik[i]的值不可能变小),每次出现环,在这个环里面只剩下一个mlik[i]没有被改变(深度最低的那个),或者全部被改变,因为那个深度最低的节点在另一个环内。那么Gabow算法中的第二堆栈变化就是删除构成环的节点,只剩深度最低的节点,或者全部删除,这个过程是通过出栈来实现,因为深度最低的那个顶点一定比前面的先访问,那么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问:为什么弹出的都是同一个强连通分量?因为在这个节点访问之前,能够构成强连通分量的那些节点已经被弹出了,这个对Tarjan算法有了解的都应该清楚,那么Tarjan算法中的判断根我们用什么来代替呢?想想,其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

    现在,你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现,但是,Gabow算法更精妙,时间更少(不用频繁更新mlik[])。 

    2.      伪代码

    Gabow_Algorithm:

               step1:

         找一个没有被访问过的节点v,goto step2(v)。否则,算法结束。

               step2(v):

                将v压入堆栈stk1[]和stk2[]

                对于v所有的邻接顶点u:

      1)     如果没有访问过,则step2(u)

      2)     如果访问过,但没有删除,维护stk2[](处理环的过程)

                如果stk2[]的顶元素==v,那么输出相应的强连通分量 

    3.      实现代码

    #include <iostream>

    using namespace std;

     

    const int MAXN = 110;

     

    typedef int AdjTable[MAXN]; //邻接表类型

     

    int      n;

    int      intm[MAXN]; //标记进入顶点时间

    int      belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

    int      stk1[MAXN]; //辅助堆栈

    int      stk2[MAXN]; //辅助堆栈

    AdjTable adj[MAXN]; //邻接表

     

    //深搜过程,该算法的主体都在这里

    void Visit(int cur, int &sig, int &scc_num)

    {

       int i;

     

       intm[cur] = ++sig;

       stk1[++stk1[0]] = cur;

       stk2[++stk2[0]] = cur;

     

       for ( i=1; i<=adj[cur][0]; ++i )

       {

          if ( 0==intm[adj[cur][i]] )

          {

              Visit(adj[cur][i],sig,scc_num);

          }

          else if ( 0==belg[adj[cur][i]] )

          {

              while ( intm[stk2[stk2[0]]]>intm[adj[cur][i]] )

              {

                 -- stk2[0];

              }

          }

       }

     

       if ( stk2[stk2[0]]==cur )

       {

          -- stk2[0]; ++ scc_num;

          do

          {

              belg[stk1[stk1[0]]] = scc_num;

          }

          while ( stk1[stk1[0]--]!=cur );

       }  

    }

     

    //Gabow算法,求解belg[1..n],且返回强连通分量个数,

    int Gabow_StronglyConnectedComponent()

    {

       int i, sig, scc_num;

     

       memset(belg+1,0,sizeof(int)*n);

       memset(intm+1,0,sizeof(int)*n);

       sig = 0; scc_num = 0; stk1[0] = 0; stk2[0] = 0; 

       for ( i=1; i<=n; ++i )

       {

          if ( 0==intm[i] )

          {

              Visit(i,sig,scc_num);

          }

       }

     

       return scc_num;

     

    四、 总结

        写到这里,做一个总结:Kosaraju算法的第二次深搜隐藏了一个拓扑性质,而Tarjan算法和Gabow算法省略了第二次深搜,所以,它们不具有拓扑性质。Tarjan算法用堆栈和标记,Gabow用两个堆栈(其中一个堆栈的实质是代替了Tarjan算法的标记部分)来代替Kosaraju算法的第二次深搜,所以只用一次深搜,效率比Kosaraju算法高。

     

    这题我使用了kosaraju算法,代码如下

     

    ContractedBlock.gifExpandedBlockStart.gifCode
    #include<stdio.h>
    #include
    <string.h>
    bool a[505][505],f[505];
    int h[505],n;
    void fv(int cur,int &s)
    {
        
    int i;
        f[cur]
    =1;
        
    for(i=1;i<=n;i++){
            
    if(a[cur][i]&&f[i]==0){
                fv(i,s);    
            }
        }
        h[
    ++s]=cur;
    }
    void sv(int cur,int s)
    {
        
    int i;
        f[cur]
    =1;

        
    for(i=1;i<=n;i++){
            
    if(a[i][cur]&&f[i]==0)
                sv(i,s);
        }
    }
    void process()
    {
        
    int i,ans;
        memset(f,
    0,sizeof(f));
        
    for(ans=0,i=1;i<=n;i++){
            
    if(f[i]==0)
                fv(i,ans);
        }
        memset(f,
    0,sizeof(f));
        
    for(ans=0,i=n;i>0;i--){
            
    if(f[h[i]]==0)
                sv(h[i],
    ++ans);
        }
        printf(
    "%d\n",ans);
    }
    int main()
    {
        
    int t,i,j,m;
        scanf(
    "%d",&t);
        
    while(t--){
            memset(a,
    0,sizeof(a));
            scanf(
    "%d %d",&n,&m);
            
    while(m--){
                scanf(
    "%d %d",&i,&j);
                a[i][j]
    =1;
            }
            process();
        }

    }

    转载于:https://www.cnblogs.com/pandy/archive/2009/05/02/1447649.html

    展开全文
  • 有向图连通分量

    2020-09-23 00:03:33
    文章目录有向图连通分量1 基本概念1.1 名词解释1.2 重要性质1.3 结论2. 板子3....有向图G极大强连通子图称为G连通分量(SCC)(单点肯定都是scc,但要使scc尽可能大,所以能大尽量大) dfn[x]数组:

    有向图强连通分量

    1 基本概念

    1.1 名词解释

    强连通分量:如果有向图中任意两点都有互相可达的路径,则此图为强连通图。有向图G的极大强连通子图称为G的强连通分量(SCC)(单点肯定都是scc,但要使scc尽可能大,所以能大尽量大)
    dfn[x]数组:时间戳,记录每一个点被dfs访问到的顺序,某个点的dfs越小,表示该点越浅,dfs数组从1开始
    low[x]:代表在dfs数中,此点以及其后代指出去的边,能返回到的最浅的点的时间戳

    Image.png

    缩点: 可以将一个强连通分量当做一个超级点,而点权按题意来定。
    示例如下:缩点前=>缩点后
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0lG6660V-1600790598463)(https://i.loli.net/2020/04/30/XFsdVIzpR9S4Pj7.png)]

    1.2 重要性质

    scc性质:
    (1).一个强连通分量内所有点的low[]值都相同
    (2).一个强连通分量的根的low[root]==dfn[root]
    (3).任何一个点的low[x]<=dfn[x]

    缩点性质:

    1. 遍历每一个点,遍历每一个点的出边,如果出边的两个端点分别在两个scc[1]和scc[2]内,那么建立一条新的边add(scc[1],scc[2]),表示这两个scc间有一条有向边;
    2. 同时缩点后,缩点的下标与拓扑序反序,因此把sccnum从大到小(即拓扑顺序)就可以进行动态规划求出很多东西,比如说方案,最长链等。

    1.3 结论

    和度有关性质

    1. 缩点后,对于新图而言,只需要往入度为0的点注入水流,整张图就可以都有水
    2. 缩点后,对于新图而言,把一张dag变为一张scc只需要添加max(入度为0的点数目,出度为0的点数目)条边
    3. 一张图中其他所有点都可达的点就是出度为0的点,因此,只需要缩点,新图中出度为0的超级点内含的点数目就是答案。
    4. 注意:当统计出度/入度为k(k > 0)的时候需要判断重边

    和dp有关的性质

    1. tarjan算法求出来的scc顺序是反拓扑序,因此可以利用这个性质做dp,即可用在tarjan算法的过程中做dp,也可由在tarjan算法进行完成后再做,且完成后做时间更优。
    2. 要求必须从起点开始,那么把起点当作tarjan算法的输入参数,求出来的所有缩点一定都是从起点开始的点
    3. 要求必须到达终点的情况,那么维护一个数组f2[i],f2[i]为1表示i能够到达终点,0表示不能到达终点。在tarjan求scc时,如果当前x点==n时,f[sccnum]=1
    4. 注意:当统计方案数的时候需要判重边

    2. 板子

    tarjan+缩点+拓扑序dp(反缩点顺序)

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e5 + 10, M = 2e6 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N];
    int n, m, x;
    int f[N], g[N];
    int scc_count[N];
    set<long long> exist;  // 本题要求方案,因此需要对新图的边去重
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) { // 遍历每一个与根节点相邻的点
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j])  { // j点没有访问过
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {// 如果j这个点还在栈内(在栈内的话不属于任何一个scc),同时一个栈内的点在一个scc内
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {  // 只有某个强连通分量的根节点的low和dfn才会相同
            sccnum++;
            while (1) {  // 出栈直到等于root
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m >> x;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k] && !exist.count(scc[i] * 100000ll + scc[k])) {  // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                    add(scc[i], scc[k], h2);
                    exist.insert(scc[i] * 100000ll + scc[k]);
                }
            }
        }
    
        // 按照缩点的逆序(拓扑序顺序)进行dp
        for (int i = sccnum; i; --i) {
            if (!f[i]) {  // 初始化
                f[i] = scc_count[i];
                g[i] = 1;
            }
            for (int j = h2[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (f[k] < f[i] + scc_count[k]) {
                    f[k] = f[i] + scc_count[k];
                    g[k] = g[i];
                }
                else if (f[k] == f[i] + scc_count[k]) g[k] = (g[k] + g[i]) % x;
            }
        }
    
        // 计算最大值
        int maxi = 0, sum = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (f[i] > maxi) {
                maxi = f[i];
                sum = g[i];
            }
            else if (f[i] == maxi) sum = (sum + g[i]) % x;
        }
        cout << maxi << "\n" << sum << endl;
    
        return 0;
    }
    

    3. 例题

    3.1 tarjan + 缩点 + 度

    P2341 受欢迎的牛
    题意: 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 A喜欢 B,B喜欢 C,那么 A 也喜欢 C。牛栏里共有 N 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。奶牛数目N~1e4, 传递关系M~5e4
    题解: 建图,缩点,建新图,然后统计新图是否是一个连通图,如果不是,那么答案为0;如果新图是一个连通图,那么统计出度为0的点的数目,如果>=2,那么答案为0;如果为1,那么为这个超级点内的点数目。
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e4 + 10, M = 1e5 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx;
    int n, m, x;
    int scc_count[N], dout[N];
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) { // 遍历每一个与根节点相邻的点
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) { // j点没有访问过
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {  // 如果j这个点还在栈内(在栈内的话不属于任何一个scc),同时一个栈内的点在一个scc内
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) { // 只有某个强连通分量的根节点的low和dfn才会相同
            sccnum++;
            while (1) {  // 出栈直到等于root
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k]) dout[scc[i]]++;
            }
        }
    
        int cnt = 0, res = 0, cow = -1;
        for (int i = 1; i <= sccnum; ++i) if (!dout[i]) cnt++, cow = i;
    
        printf("%d", (cnt >= 2? 0: scc_count[cow]));
    
        return 0;
    }
    

    acwing367 学校网络
    题意: 给定一个有向图:N个点,求:
    1)至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点
    2)至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点
    题解: 先缩点
    第一问:只需要往入度为0的点放入,即可到达其他所有的点
    第二问:max(入度为0的点的数目,出度为0的点数目)
    注意要特判下缩点后只有一个scc的情况
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e2 + 10, M = N * N;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx;
    int n, m, dout[N], din[N];
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            while (1) {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n;
        memset(h1, -1, sizeof h1);
        for (int i = 1, t; i <= n; ++i) {
            while (scanf("%d", &t) && t) add(i, t, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k]) dout[scc[i]]++, din[scc[k]]++;
            }
        }
        
        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (!dout[i]) cnt1 ++;
            if (!din[i]) cnt2 ++;
        }
        
        printf("%d\n%d\n", max(1, cnt2), (sccnum == 1? 0: max(cnt1, cnt2)));
        return 0;
    }
    

    acwing401从u到v还是从v到u?
    题意: 给定一个 n 个点 m 条边的有向图,现在要求图中任意两点u和v,均可满足u能通往v或v能通往u,请你判断要求是否能够成立。 0<n<1001,m<6000
    题解: 一张有向图的中任意两个点u和v,均可满足u能通往v或v能通往u,那么这个有向图缩点后做拓扑排序每次队列里的元素个数小于等于1
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 2e3 + 10, M = 2e4 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N], din[N], n, m, t;
    set<long long> exist;  // 本题要求方案,因此需要对新图的边去重
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            while (1)  {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    bool top_sort() {
        queue<int> q;  // 维护一个队列
        for (int i = 1; i <= sccnum; ++i) if (!din[i]) q.push(i);  // 把入度为0的点加入队列
        // 当队列不为空时
        while (q.size()) {
            if (q.size() > 1) return 0;
            auto t = q.front();  // 取队头
            q.pop();  // 队头出队
            for (int i = h2[t]; i != -1; i = ne[i]) {
                int j = e[i];
                din[j]--;  // 队头元素出队相当于把与队头元素相连的元素的入度减一
                if (!din[j]) q.push(j);  // 把入度为0的元素放入队列
            }
        }
        return 1;
    }
    
    int main() {
        cin >> t;
        while (t--) {
            cin >> n >> m;
            memset(h1, -1, sizeof h1);
            memset(h2, -1, sizeof h2);
            memset(dfn, 0, sizeof dfn);
            memset(scc, 0, sizeof scc);
            memset(din, 0, sizeof din);
            idx = timestamp = sccnum = 0;
            exist.clear();
            for (int i = 1; i <= m; ++i) {
                int a, b;
                scanf("%d %d", &a, &b);
                add(a, b, h1);
            }
        
            // tarjan求scc
            for (int i = 1; i <= n; ++i)
                if (!dfn[i]) tarjan(i, h1);
            
            // 缩点
            for (int i = 1; i <= n; ++i) {
                for (int j = h1[i]; j != -1; j = ne[j]) {
                    int k = e[j];
                    if (scc[i] != scc[k] && !exist.count(scc[i] * 100000ll + scc[k])) {  // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                        add(scc[i], scc[k], h2);
                        exist.insert(scc[i] * 100000ll + scc[k]);
                        din[scc[k]]++;
                    }
                }
            }
            
            if (top_sort()) cout << "Yes\n";
            else cout << "No\n";
        }
    
        return 0;
    }
    

    acwing402杀人游戏
    题意: 有N个人,其中一个杀手,其余都是平民。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的所有人当中,谁是杀手,谁是平民。假如查证的对象是杀手, 杀手将会把警察干掉。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?给定M个关系,每行两个整数 x,y,表示 x 认识 y。1≤N≤105,0≤M≤3∗105
    题解: 分析可知,缩点后,每次从入度为0的点开始搜索,那么可能死亡的概率最小,且只有从链头开始搜索的时候发生一次,警察死的概率为入度为0的点数目/总点数,需要特判一种情况。
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 2e5 + 10, M = 6e5 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N];
    int n, m;
    int scc_count[N], din[N], dout[N];
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j])  {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root])  {
            sccnum++;
            while (1) {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int check(int u) {
        if (scc_count[u] != 1) return 0;
        if (!dout[u]) return 1;
        
        for (int i = h2[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (din[j] == 1) return 0;
        }
        return 1;
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k]) {  // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                    din[scc[k]] ++;
                    dout[scc[i]] ++;
                    add(scc[i], scc[k], h2);
                }
            }
        }
        
        int ans = 0, f = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (!din[i]) ans++;
        }
        
        // 特判
        for (int i = 1; i <= sccnum; ++i) {
            if (!f && !din[i] && check(i)) f = 1;
        }
        
        printf("%.6f", 1 - (double)(ans - f) / n);
    
        return 0;
    }
    

    3.2 tarjan + 缩点 + dp

    3.2.1 求最长链、求方案数

    acwing1175 最大半连通子图
    题意: 求最大半连通子图的节点数以及方案数。
    最大半连通子图:对于G的子图,如果u,v满足u->v或v->u的关系,且这个子图最大,那么就是最大半连通子图。节点数N~1e5, 边数M~1e6
    题解: 最大半连通子图就是最长链,即求最长链的长度及方案。本题缩点完求最长链的长度和方案,因此缩点完dp处理即可,f[i]表示到i点的最长链的长度,g[i]表示到i点的最长链的方案。由于缩点完之后点的下标就是按拓扑序的逆序的,因此可以按照逆序进行dp处理。处理的方法参加背包问题求方案数
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e5 + 10, M = 2e6 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx,h2[N];
    int n, m, x;
    int f[N], g[N];  // f[i]从s出发,i的最长链长度;g[i]从s出发,i的最长链方案;
    int scc_count[N];
    set<long long> exist;  // 本题要求方案,因此需要对新图的边去重
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root])  {
            sccnum++;
            while (1)  {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m >> x;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k] && !exist.count(scc[i] * 100000ll + scc[k])) { // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                    add(scc[i], scc[k], h2);
                    exist.insert(scc[i] * 100000ll + scc[k]);
                }
            }
        }
    
        // 按照缩点的逆序(拓扑序顺序)进行dp
        for (int i = sccnum; i; --i) {
            if (!f[i]) {
                f[i] = scc_count[i];
                g[i] = 1;
            }
            for (int j = h2[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (f[k] < f[i] + scc_count[k]) {
                    f[k] = f[i] + scc_count[k];
                    g[k] = g[i];
                }
                else if (f[k] == f[i] + scc_count[k]) g[k] = (g[k] + g[i]) % x;
            }
        }
    
        // 计算最大值
        int maxi = 0, sum = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (f[i] > maxi) {
                maxi = f[i];
                sum = g[i];
            }
            else if (f[i] == maxi) sum = (sum + g[i]) % x;
        }
        cout << maxi << "\n" << sum << endl;
    
        return 0;
    }
    

    3.2.2 求解差分约束

    acwing1169糖果
    题意:
    幼儿园里有 N 个小朋友,老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。老师需要满足小朋友们的 K 个要求。老师想知道他至少需要准备多少个糖果。
    要求有5种:
    如果 X=1.表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多。
    如果 X=2,表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。
    如果 X=3,表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。
    如果 X=4,表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。
    如果 X=5,表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。
    N~1e5, K~1e5, 1 <=A, B <= N
    题解: 原来的思路是建图后,做差分约束,跑spfa,一旦发现出现正环那么无解,否则求出最长距离,然后累加,这种方法时间卡在spfa上,
    spfa有可能跑出O(nm)的时间导致超时
    由于数据比较特殊,只有0和1两种,那么可以换一个方法:
    对于每一个环,它一定是属于scc,而只要出现1条边权为1的边那么就是出现正环,所有我们可以缩点后,判断每个scc内部是否出现
    边权为1的边,一旦出现就是正环,无解;如果没有出现,那么有解,求完scc后缩点,然后按照缩点的逆序(拓扑序)进行dp,求出
    最长链dis,然后答案就是每个超级点内点的个数*这个点的最长距离的累加值。
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    int const N = 1e5 + 10, M = 6e5 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], h2[N], e[M], ne[M], idx, w[M];
    int n, m;
    int scc_count[N];
    int dis[N];
    
    // a->b有一条边
    void add(int a, int b, int c, int h[]) {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i])  {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j])  {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            while (1) {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
    
        // 建图
        for (int i = 0, x, a, b; i < m; ++i) {
            scanf("%d %d %d", &x, &a, &b);
            if (x == 1) add(a, b, 0, h1), add(b, a, 0, h1);
            else if (x == 2) add(a, b, 1, h1);
            else if (x == 3) add(b, a, 0, h1);
            else if (x == 4) add(b, a, 1, h1);
            else if (x == 5) add(a, b, 0, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) scc_count[scc[i]] ++;
        
        // 缩点建图(顺便判断是否有解)
        bool success = true;
        for (int i = 1; i <= n; i ++ ) {
            for (int j = h1[i]; ~j; j = ne[j]) {
                int k = e[j];
                int a = scc[i], b = scc[k];
                if (a == b) {
                    if (w[j] > 0) {
                        success = false;
                        break;
                    }
                }
                else add(a, b, w[j], h2);
            }
            if (!success) break;
        }
    
        // 做dp求最长路
        if (!success) puts("-1");
        else {
            for (int i = sccnum; i; i--) dis[i] = 1;
            for (int i = sccnum; i; i -- ) {
                for (int j = h2[i]; ~j; j = ne[j]) {
                    int k = e[j];
                    dis[k] = max(dis[k], dis[i] + w[j]);
                }
            }
    
        // 求答案
        LL res = 0;
        for (int i = 1; i <= sccnum; i ++ ) res += (LL)dis[i] * scc_count[i];
        printf("%lld\n", res);
        }
        return 0;
    }
    

    3.2.3 求解必经点问题

    acwing341最优贸易
    题意: 给出 n个城市的水晶球价格,m 条道路的信息。在1->N路径(可以不简单)上买1次卖1次,最多能赚多少钱。
    题解: 本题要找1 ~ n上最大的点和最小的点
    考虑dp求解,维护数组f1[i]表示i点开始到n点的最大价值,然后去枚举i为买的点,答案即为max{val[i]-f1[i]}
    但是本题可能存在环,因此考虑tarjan算法缩点变成dag
    本题的难点在于要求当前的点i必须是从1开始,到n结束
    从1开始好处理,tarjan算法的时候只做1为起点的tarjan,这样求出来的都是从1开始的
    而到n结束就必须维护一个数组f2[i]表示i是否能够到n点,f2[i]为1表示i能够到n点,为0表示不能到n点,每次都必须更新f2
    维护数组f1[i]表示i点开始到n点的最大价值,当且仅当f2[i]=1才能转移,f1[i]=max[max{f1[u]}, val[i]]
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    int const N = 2e5 + 10, M = 2e6 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N], w[N];
    int n, m;
    int f1[N], f2[N]; //f1[i]表示i点开始到n点的最大价值, f2[i]为1表示i能够到n点,为0表示不能到n点
    PII scc_count[N];  // first为max,second为min
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }   
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j])  {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j])  {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            scc_count[sccnum].first = -1;  // 计算最大值和最小值
            scc_count[sccnum].second = 1e9;
            while (1) {
                int x = stk[top--];
                if (x == n) f2[sccnum] = 1;
                scc[x] = sccnum;
                scc_count[sccnum].first = max(scc_count[sccnum].first, w[x]);
                scc_count[sccnum].second = min(scc_count[sccnum].second, w[x]);
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        memset(f1, -1, sizeof f1);
        
        for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        for (int i = 1, a, b, t; i <= m; ++i) {
            scanf("%d %d %d", &a, &b, &t);
            add(a, b, h1);
            if (t == 2) add(b, a, h1);
        }
    
        // tarjan求scc
        tarjan(1, h1);  // 这样保证后面缩点的所有点都是从1开始
        
        // 缩点
        for (int i = 1; i <= n; ++i)
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k] && scc[i] && scc[k]) add(scc[i], scc[k], h2);
            }
        
        // 反拓扑序做dp
        int ans = 0;
        for (int i = 1; i <= sccnum; ++i) {  
            int maxv = -1;
            for (int j = h2[i]; ~j; j = ne[j]) {
                int k = e[j];
                f2[i] |= f2[k];  // 更新i是否能够到达终点的情况
                if (f2[k]) maxv = max(maxv, f1[k]);  // 更新能够到达终点的最大值
            }
            if (f2[i]) {  // 只要f2为1才更新
                f1[i] = max(scc_count[i].first, maxv);
                ans = max(ans, f1[i] - scc_count[i].second);
            }
        }
    
        cout << ans;
    
        return 0;
    }
    
    展开全文
  • 有向图强连通分量的Tarjan算法 [有向图强连通分量] ...非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一个强连通分量,因为顶...
  • 有向图连通分量的Tarjian算法

    千次阅读 2018-08-09 09:51:49
    有向图强连通分量的Tarjian算法 2016年08月16日 10:38:45 阅读数:2006 ... [有向图强连通分量] 在有向图G中,如果两个顶点间至少存在一条...非强连通图有向图的极大强连通子图,称为强连通分量(strongly connect...
  • 有向图的连通分量 1.强连通 代表的是 这个连通块中的每两个点互相都是有一条路径是可以走到的 2.分量 就是子图; 从这张图上可以看出 A B C这三个点都是互相可以走到的 所以他们就是一个联通块 D E F 三个点都是...
  • Tarjan有向图强连通分量 本文仅供娱乐,不喜勿喷 一、强连通分量 有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有...有向图的极大强连通子图,称为强连通分量(strongly connect...
  • 有向图的连通分量是由相互均为强连通顶点的最大子集构成的. 强连通分量搜索算法:Kosaraju 首先, 定义有向图GGG的反向图GRG^RGR.由有向图GGG中每一条有向边v−>wv->wv−>w取反的反向边...
  • 有向图强连通分量的Tarjan算法 [有向图强连通分量] ...非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一个强连通分量,因为

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,793
精华内容 1,517
关键字:

有向图的连通分量