題意：給你一個連通圖，然後再給你n個詢問，每個詢問給一個點u,v表示加上u,v之後又多少個橋。一個最容易想到的辦法就是先加邊找橋，加邊找橋，這樣可定逾時。那麼就可以縮點，因為如果一條邊不是橋那麼無論怎麼加邊他肯定都不會變成橋，這樣我吧不是橋的點縮成一個點。這樣全圖就都是橋，這樣的話，我們就在加的遍裡面去找如果加的邊是同一個點，那麼，肯定不會減少橋，但是如果不是同一個，那麼橋肯定減少~。
代碼如下：
1 #include <stdio.h>
2 #include <string.h>
3 #include <iostream>
4 #include <algorithm>
5 #include <stdlib.h>
6 #include <vector>
7 #include <queue>
8 #define loop(s,i,n) for(i = s;i < n;i++)
9 #define cl(a,b) memset(a,b,sizeof(a))
10 using namespace std;
11 const int maxn = 100005;
12 int low[maxn],dfn[maxn],set[maxn],father[maxn],dfsclock,cut;
13 vector<int >g[maxn];
14 int find(int x)
15 {
16 if(set[x] != x)
17 set[x] = find(set[x]);
18
19 return set[x];
20 }
21 int merge(int x,int y)
22 {
23 x = find(x);
24 y = find(y);
25 if(y != x)
26 {
27 set[y] = x;
28 return 1;
29 }
30 return 0;
31 }
32
33 void tarjan(int u,int pre)
34 {
35 int v,i,j;
36 dfn[u] = low[u] = ++dfsclock;
37 loop(0,i,g[u].size())
38 {
39 v = g[u][i];
40 if(!dfn[v])
41 {
42 tarjan(v,u);
43 father[v] = u;
44 low[u] = min(low[v],low[u]);
45 if(low[v] > dfn[u])
46 cut++;
47 else
48 merge(u,v);
49 }
50 else if(v != pre)
51 low[u] = min(low[u],dfn[v]);
52 }
53 }
54 void lca(int u,int v)
55 {
56
57 while(u != v)
58 {
59 while(dfn[u] >= dfn[v] && u != v)
60 {
61 if(merge(u,father[u]))
62 cut--;
63 u = father[u];
64 }
65 while(dfn[v] >= dfn[u] && u != v)
66 {
67 if(merge(v,father[v]))
68 cut--;
69 v = father[v];
70 }
71 }
72 }
73 int main()
74 {
75 int n,m;
76 int i,x,y,cas = 0;
77 while(scanf("%d %d", &n,&m)&&(n||m))
78 {
79 int u,v;
80 printf("Case %d:\n",++cas);
81 loop(1,i,n+1)
82 {
83 g[i].clear();
84 set[i] = i;
85 father[i] = 0;
86 }
87 while(m--)
88 {
89 scanf("%d %d",&u,&v);
90 g[u].push_back(v);
91 g[v].push_back(u);
92
93 }
94 cl(dfn,0);
95 cl(low,0);
96 cut = dfsclock = 0;
97
98 int k;
99 scanf("%d",&k);
100 tarjan(1,-1);
101
102 while(k--)
103 {
104 scanf("%d %d",&u,&v);
105 lca(u,v);
106 printf("%d\n",cut);
107 }
108 puts("");
109 }
110 return 0;
111 } View Code
轉載于:https://www.cnblogs.com/0803yijia/p/3227711.html