本文共 2603 字，大约阅读时间需要 8 分钟。
题意：给定一个连通的无向图G，至少要添加几条边，才能使其变为双连通图。
链接：
kuangbin模板题，分析链接：
1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int MAXN = 5010;//点数 8 const int MAXM = 20010;//边数，因为是无向图，所以这个值要*2 9 struct Edge 10 { 11 int to,next; 12 bool cut;//是否是桥标记 13 }edge[MAXM]; 14 int head[MAXN],tot; 15 int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block 16 int Index,top; 17 int block;//边双连通块数 18 bool Instack[MAXN]; 19 int bridge;//桥的数目 20 void addedge(int u,int v) 21 { 22 edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false; 23 head[u] = tot++; 24 } 25 void Tarjan(int u,int pre) 26 { 27 int v; 28 Low[u] = DFN[u] = ++Index; 29 Stack[top++] = u; 30 Instack[u] = true; 31 for(int i = head[u];i != -1;i = edge[i].next) 32 { 33 v = edge[i].to; 34 if(v == pre)continue; 35 if( !DFN[v] ) 36 { 37 Tarjan(v,u); 38 if( Low[u] > Low[v] )Low[u] = Low[v]; 39 if(Low[v] > DFN[u]) 40 { 41 bridge++; 42 edge[i].cut = true; 43 edge[i^1].cut = true; 44 } 45 } 46 else if( Instack[v] && Low[u] > DFN[v] ) 47 Low[u] = DFN[v]; 48 } 49 if(Low[u] == DFN[u]) 50 { 51 block++; 52 do 53 { 54 v = Stack[--top]; 55 Instack[v] = false; 56 Belong[v] = block; 57 } 58 while( v!=u ); 59 } 60 } 61 void init() 62 { 63 tot = 0; 64 memset(head,-1,sizeof(head)); 65 } 66 int du[MAXN];//缩点后形成树，每个点的度数 67 void solve(int n) 68 { 69 memset(DFN,0,sizeof(DFN)); 70 memset(Instack,false,sizeof(Instack)); 71 Index = top = block = 0; 72 Tarjan(1,0); 73 int ans = 0; 74 memset(du,0,sizeof(du)); 75 for(int i = 1;i <= n;i++) 76 for(int j = head[i];j != -1;j = edge[j].next) 77 if(edge[j].cut) 78 du[Belong[i]]++; 79 for(int i = 1;i <= block;i++) 80 if(du[i]==1) 81 ans++; 82 //找叶子结点的个数ans,构造边双连通图需要加边(ans+1)/2 83 printf("%d\n",(ans+1)/2); 84 } 85 int main() 86 { 87 int n,m; 88 int u,v; 89 while(scanf("%d%d",&n,&m)==2) 90 { 91 init(); 92 while(m--) 93 { 94 scanf("%d%d",&u,&v); 95 addedge(u,v); 96 addedge(v,u); 97 } 98 solve(n); 99 }100 return 0;101 }
转载于:https://www.cnblogs.com/cnblogs321114287/p/4617796.html