微网站开发报价,wordpress 视频弹窗,百度提交网址入口,模拟创建一个公司1 /*2 题意#xff1a;给定一个连通的无向图G#xff0c;至少要添加几条边#xff0c;才能使其变为强连通图#xff08;指的是边强联通#xff09;。 3 思路#xff1a;利用tarjan算法找出所有的双联通分量#xff01;然后根据low[]值的不同将双联通分量4 进行… 1 /*2 题意给定一个连通的无向图G至少要添加几条边才能使其变为强连通图指的是边强联通。 3 思路利用tarjan算法找出所有的双联通分量然后根据low[]值的不同将双联通分量4 进行缩点最后图形会变成一棵树也就是添加至少多少条边使一棵树变成强联通图 5 6 知识点若要使得任意一棵树在增加若干条边后变成一个双连通图那么7 至少增加的边数 这棵树总度数为1的结点数 1 / 2 8 9 */
10 #includeiostream
11 #includecstring
12 #includecstdio
13 #includealgorithm
14 #includevector
15 #define N 1005
16 using namespace std;
17 vectorintg[N];
18 int low[N], pre[N];
19 int deg[N];
20 int n, m;
21 int cnt;
22 int dfsClock;
23 void dfs(int u, int fa){
24 low[u]pre[u]dfsClock;
25 int leng[u].size();
26 for(int i0; ilen; i){
27 int vg[u][i];
28 if(!pre[v]){
29 dfs(v, u);
30 low[u]min(low[u], low[v]);
31 }
32 else if(pre[v] pre[u] fa!v)
33 low[u]min(pre[v], low[u]);
34 }
35 }
36
37 int main(){
38 while(scanf(%d%d, n, m)!EOF){
39 memset(pre, 0, sizeof(pre));
40 memset(deg, 0, sizeof(deg));
41 while(m--){
42 int u, v;
43 scanf(%d%d, u, v);
44 g[u].push_back(v);
45 g[v].push_back(u);
46 }
47 cnt0;
48 dfsClock0;
49 dfs(1, -1);
50 for(int i1; in; i){
51 int leng[i].size();
52 for(int j0; jlen; j){
53 int vg[i][j];
54 if(low[i]!low[v])
55 deg[low[i]];
56 }
57 }
58 for(int i1; in; i)
59 if(deg[i]1)
60 cnt;
61 printf(%d\n, (cnt1)/2);
62 for(int i1; in; i)
63 g[i].clear();
64 }
65 return 0;
66 } 转载于:https://www.cnblogs.com/hujunzheng/p/3909568.html
