tarjan算法（割点/割边/点连通分量/边连通分量/强连通分量）-白红宇

tarjan算法（割点/割边/点连通分量/边连通分量/强连通分量）

阅读量：5377 次

发布时间：2019-06-15

本文共 5369 字，大约阅读时间需要 17 分钟。

tarjan算法是在dfs生成一颗dfs树的时候按照访问顺序的先后，为每个结点分配一个时间戳，然后再用low[u]表示结点能访问到的最小时间戳

以上的各种应用都是在此拓展而来的。

割点：如果一个图去掉某个点，使得图的连通分支数增加，那么这个点就是割点

某个点是割点，当且仅当这个点的后代没有连回自己祖先的边。即low[v] >= dfn[u] ， v是u的后代

需要注意的是根结点的特判，因为根结点没有祖先，根结点是割点，当且仅当根结点有两个以上的儿子。

问题：重边对该算法有影响吗？没有影响。

　　　需要注意的地方？图至少有三个点以上，否则需要注意一下。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 typedef long long LL; 15 const int INF = 1<<30;16 const int N = 1000 + 10;17 vector
                  
                    g[N];18 int dfs_clock,dfn[N],low[N];19 bool isCut[N];20 void init(int n)21 {22 dfs_clock = 0;23 for(int i=0; i<=n; ++i)24 dfn[i] = low[i] = isCut[i] = 0;25 }26 //重边对割点没有影响，且该算法对有向图同样适用27 void tarjan(int u, int fa)28 {29 dfn[u] = low[u] = ++dfs_clock;30 int child = 0;31 for(int i=0; i
                   
                    = dfn[u])40 isCut[u] = true;41 }42 if(fa==-1 && child>=2) isCut[u] = true;43 }44 int main()45 {46 int n,m,i,u,v;47 while(scanf("%d%d",&n,&m)!=EOF)48 {49 init(n);50 for(i=0; i

View Code

割边：如果一个图去掉某条边，使得图的连通分支数增加，那么这条边就是割边（桥）

某条边是割边，当且仅当某个点的后代没有连回自己或者自己祖先的边，即low[v] > dfn[u], 那么边(u,v)是割边

问题：重边对该算法有影响吗？有影响。所以要判断是不是有重边

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 typedef long long LL; 15 const int INF = 1<<30;16 const int N = 1000 + 10;17 vector
                  
                    g[N];18 int dfs_clock,dfn[N],low[N],cntCut;19 void init(int n)20 {21 cntCut = dfs_clock = 0;22 for(int i=0; i<=n; ++i)23 {24 dfn[i] = low[i] = 0;25 g[i].clear();26 } 27 }28 //重边对割边有影响，比如有2--3 ,2--3两条边，那么边2--3就不是割边，因为去掉还是连通的，所以要判断一下29 void tarjan(int u, int fa)30 {31 dfn[u] = low[u] = ++dfs_clock;32 bool flag = false;33 for(int i=0; i
                   
                     dfn[u])//这里统计的是割边的数量，如果要记录割边，那么就标记边，或者把边入栈45 cntCut++;46 }47 }48 int main()49 {50 int n,m,i,u,v;51 while(scanf("%d%d",&n,&m)!=EOF)52 {53 init(n);54 for(i=0; i

View Code

点-双连通分量：如果任意两点存在两条点不重复的路径，那么就说这个图是点-双连通的。点-双连通的极大子图称为双连通分量

双连通分量之间的分界点是割点。而且双连通分量不可能分布在树根结点两端。所以我们将边入栈，当遇到割点时，就将边出栈，直到有边等于当前边。就跳出

问题：重边对该算法有影响吗？没有影响

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 using namespace std; 14 typedef long long LL; 15 const int INF = 1<<30; 16 const int N = 1000 + 10; 17 struct Edge 18 { 19 int u,v; 20 Edge(){}; 21 Edge(int u, int v) 22 { 23 this->u = u; 24 this->v = v; 25 } 26 }; 27 vector
                  
                    g[N],bcc[N]; 28 int bccno[N],dfn[N],low[N],dfs_clock,cnt; 29 stack
                   
                     st; 30 void init(int n) 31 { 32 cnt = dfs_clock = 0; 33 for(int i=0; i<=n; ++i) 34 { 35 bccno[i] = low[i] = dfn[i] = 0; 36 bcc[i].clear(); 37 g[i].clear(); 38 } 39 } 40 void tarjan(int u, int fa) 41 { 42 dfn[u] = low[u] = ++dfs_clock; 43 for(int i=0; i
                    
                     = dfn[u])//如果这个点是割点，那么先前入栈的一些边是属于一个双连通分量的 52 { 53 Edge x; 54 cnt++; 55 for(;;) 56 { 57 x = st.top(); 58 st.pop(); 59 if(bccno[x.u] != cnt) 60 { 61 bccno[x.u] = cnt; 62 bcc[cnt].push_back(x.u); 63 } 64 if(bccno[x.v] != cnt) 65 { 66 bccno[x.v] = cnt; 67 bcc[cnt].push_back(x.v); 68 } 69 if(x.u==u && x.v==v) 70 break; 71 } 72 } 73 } 74 else if(v!=fa && dfn[v] < dfn[u]) 75 { 76 st.push(Edge(u,v)); 77 low[u] = min(low[u],dfn[v]); 78 } 79 80 } 81 } 82 int main() 83 { 84 int n,m,i,u,v; 85 while(scanf("%d%d",&n,&m)!=EOF) 86 { 87 init(n); 88 for(i=0; i

View Code

边-双连通分量：如果任意两点存在两条边不重复的路径，那么就说这个图是边-双连通的，边-双连通的极大子图成为边双连通分量。

边双连通分量的分界点是割边。双连通分量可以分布在根结点的两端。所以不能在for(int i=0; i<g[u].size(); ++i) 这个循环里面判断割边，而要在外面递归返回时判断

问题：重边对该算法有影响吗？有影响，就好像影响割边算法一样

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 typedef long long LL; 15 const int INF = 1<<30;16 const int N = 1000 + 10;17 vector
                  
                    g[N];18 stack
                   
                     st;19 int dfn[N],low[N],dfs_clock,bccno[N],cnt;20 void init(int n)21 {22 cnt = dfs_clock = 0;23 for(int i=0; i

View Code

问添加最少多少条边，使得整个图边-双连通，首先求出边-双连通分量，然后缩点，最后变成一棵树，那么要加的边就是（叶子结点+1)/2

强连通分量：如果有向图的任意两点可以，那么就说这个图是强连通的，一个图的极大子图是强连通的，那么就说这个子图是强连通分量

对于一个scc，我们要判断哪个点是该scc最先被发现的点，然后将后来发现的点出栈，知道遇到这个点。那么出栈的点都属于一个强连通分量

问题：重边对该算法有影响吗？没有影响

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 using namespace std;14 typedef long long LL; 15 const int INF = 1<<30;16 const int N = 1000 + 10;17 vector
                  
                    g[N];18 stack
                   
                     st;19 int cnt,dfs_clock,dfn[N],low[N],sccno[N];20 void init(int n)21 {22 cnt = dfs_clock = 0;23 for(int i=0; i<=n; ++i)24 {25 dfn[i] = low[i] = sccno[i] = 0;26 g[i].clear();27 }28 }29 30 void tarjan(int u, int fa)31 {32 dfn[u] = low[u] = ++dfs_clock;33 st.push(u);34 for(int i=0; i

View Code

转载于:https://www.cnblogs.com/justPassBy/p/4442144.html

你可能感兴趣的文章