題干：

There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.?
Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.

Input

The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.?
You can assume that there is no loop and no multiple edges.?
The last test case is followed by two zeros on a single line, which means the end of the input.

Output

Output the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample.

Sample Input

8 10 0 1 1 2 2 3 3 0 3 4 4 5 5 6 6 7 7 4 5 7 0 0

Sample Output

1 5

題目大意：

有一個公園有n個景點，公園的管理員準備修建m條道路，并且安排一些形成回路的參觀路線。如果一條道路被多條道路公用，那么這條路是沖突的；如果一條道路沒在任何一個回路內，那么這條路是多余的 問分別有多少條有沖突的路和多余的路（輸出要求先輸出多余的路再輸出沖突的路）

解題報告：

首先我們可以知道多余邊就是該無向圖中的橋,橋必然不在任何環(huán)中。

沖突邊只能在點雙連通分量中,而什么樣的點雙連通分量有沖突邊呢?

下面怎么判斷呢？思路過程是這樣的：（這個思想很精彩呀）

先手動找一個臨界點（憑感覺）對于有n個節(jié)點和n條邊(或小于n條邊，比如2點1邊)的點雙連通分量，這種分量只有一個大環(huán)，不存在其他任何環(huán)了，所以這種分量中的邊都不是沖突邊。

?對于有n個節(jié)點和m條邊(m>n)的點雙連通分量來說，有了剛剛的鄰接點，這個就很好判斷了。該分量內的所有邊都是沖突邊.因為邊數(shù)>點數(shù),所以該分量必有至少兩個環(huán),我們隨便畫個圖就可知其中的任意邊都至少在兩個以上的環(huán)上.

???????綜上所述,對于多余邊,我們輸出橋數(shù).對于沖突邊,我們輸出邊數(shù)>點數(shù)的點雙連通分量的所有邊數(shù).

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int n,m; int dfn[MAX],low[MAX],col[MAX]; int index,clk,bcc; int ans1,ans2,num[MAX]; struct Edge {int u,v;Edge(int u=0,int v=0):u(u),v(v){} } stk[MAX]; void init() {for(int i = 0; i<=n; i++) {vv[i].clear();dfn[i]=low[i]=col[i]=0;}clk = index = bcc = 0;ans1=ans2=0; } bool vis[MAX]; void cal(int tot) {//當前點雙連通分量共有tot個點（當然，其中可能有重疊點） (不對，應該是沒有重復點？不然后面不能直接sum > tot 來判斷啊？)int sum = 0;//當前點雙連通分量共有sum條邊 memset(vis,0,sizeof vis);for(int i = 1; i<=tot; i++) vis[num[i]] = 1;for(int i = 1; i<=tot; i++) {int u = num[i];int up = vv[u].size();for(int j = 0; j<up; j++) {if(vis[vv[u][j]]) sum++;}}sum /= 2;//因為是無向圖所以要除以2 if(sum > tot) ans2 += sum; } void tarjan(int x,int rt) {dfn[x] = low[x] = ++clk;int up = vv[x].size();for(int i = 0; i<up; i++) {int v = vv[x][i];if(v == rt) continue;//這題說了無自環(huán)無重邊，所以可以直接這樣判斷 if(dfn[v] == 0) {stk[++index] = Edge(x,v);tarjan(v,x);low[x] = min(low[x],low[v]);if(low[v] >= dfn[x]) {bcc++;int cnt = 0;while(1) {Edge tmp = stk[index];index--;if(col[tmp.u] != bcc) {num[++cnt] = tmp.u;col[tmp.u] = bcc;}if(col[tmp.v] != bcc) {num[++cnt] = tmp.v;col[tmp.v] = bcc;}if(tmp.u == x && tmp.v == v) break;}cal(cnt);}}else if(dfn[v] < dfn[x]) {//這里必須是兩個dfn！ 也不能直接寫else stk[++index] = Edge(x,v);low[x] = min(low[x],dfn[v]);}if(low[v] > dfn[x]) ans1++; //這句放到dfn[v]==0那里也可以 ，放到這里應該也沒錯！ } } int main() {while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 0; i<n; i++) {if(dfn[i] == 0) tarjan(i,-1);//因為題目保證是連通圖所以其實可以直接tarjan(1,-1)的 }printf("%d %d\n",ans1,ans2);}return 0 ; }

有幾點要注意：

1.cal函數(shù)中的這個tot（也就是tarjan函數(shù)中的cnt），是可以直接代表當前點雙連通分量中的點數(shù)的，不會有重復，因為你在if(col[tmp.u] != bcc)中都判掉了，這里非常巧妙！不能寫成if(col[tmp.u] == 0) 則染色。而應該寫成if(col[tmp.u]!=bcc) 則染成當前bcc。原因也很簡單，就是一個點可能屬于多個bcc！！！但是同一時間只可能會操作同一個bcc（也就是同一層的函數(shù)中，只可能會判斷出一個bcc來，也就是說bcc這個變量不會發(fā)生變化），所以要染色成當前操作的bcc的時候，直接判斷是否等于當前bcc就好了。這個寫法非常精彩！

2.那里不能直接寫else，因為這個情況：（假設是直接else了）

首先很顯然5，1是割點，6->5->1->2->3->4了之后把這六條邊全都壓棧，然后回溯到1的時候發(fā)現(xiàn)1是割點，記錄一下，并且③④⑤⑥全部出棧，然后再走1-4這條邊，就直接進入else壓棧了（也就是這一步錯了，因為本身不該壓棧的）。然后回溯回5，發(fā)現(xiàn)5是割點(因為low[1]>=dfn[5]成立，說明5是割點！不要認為說明1是割點！你要知道你遍歷的時候是5是父節(jié)點1是子節(jié)點！)，然后記錄一下，②⑥出棧（這時候⑥又被計算了一次。要知道雖然是點雙，所以每個頂點可能被計算多次，但是每條邊依舊是只能被計算一次！所以被計算兩次就是個錯誤，更何況5號點和⑥號邊，半毛錢關系都沒有，隔著老遠咧。）

?

3.同樣是這個地方，也不能像一般的求割點那樣，寫成else if(dfn[v] < low[x])！！！因為這種情況：

你如果這樣寫，那⑥⑦這個邊就沒法處理了

?

其實仔細思考，為什么要在這里加上一步邊入棧，其實就是想把所有的邊都考慮進去。但是進一步想，加邊進去最終的目的，還是要選出所有的點出來，而加最后一步邊的兩個點，肯定都屬于之前的兩條邊了，所以最后這一條邊加不加都可以。綜上，我又嘗試了一下直接去掉這一步加邊，后來發(fā)現(xiàn)也AC了。代碼如下：

AC代碼2：（復習的時候看這個就行）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; vector<int> vv[MAX]; int n,m; int dfn[MAX],low[MAX],col[MAX]; int index,clk,bcc; int ans1,ans2,num[MAX]; struct Edge {int u,v;Edge(int u=0,int v=0):u(u),v(v){} } stk[MAX]; void init() {for(int i = 0; i<=n; i++) {vv[i].clear();dfn[i]=low[i]=col[i]=0;}clk = index = bcc = 0;ans1=ans2=0; } bool vis[MAX]; void cal(int tot) {//當前點雙連通分量共有tot個點（當然，其中可能有重疊點） (不對，應該是沒有重復點？不然后面不能直接sum > tot 來判斷啊？)int sum = 0;//當前點雙連通分量共有sum條邊 memset(vis,0,sizeof vis);for(int i = 1; i<=tot; i++) vis[num[i]] = 1;for(int i = 1; i<=tot; i++) {int u = num[i];int up = vv[u].size();for(int j = 0; j<up; j++) {if(vis[vv[u][j]]) sum++;}}sum /= 2;//因為是無向圖所以要除以2 if(sum > tot) ans2 += sum; } void tarjan(int x,int rt) {dfn[x] = low[x] = ++clk;int up = vv[x].size();for(int i = 0; i<up; i++) {int v = vv[x][i];if(v == rt) continue;//這題說了無自環(huán)無重邊，所以可以直接這樣判斷 if(dfn[v] == 0) {stk[++index] = Edge(x,v);tarjan(v,x);low[x] = min(low[x],low[v]);if(low[v] >= dfn[x]) {bcc++;int cnt = 0;while(1) {Edge tmp = stk[index];index--;if(col[tmp.u] != bcc) {num[++cnt] = tmp.u;col[tmp.u] = bcc;}if(col[tmp.v] != bcc) {num[++cnt] = tmp.v;col[tmp.v] = bcc;}if(tmp.u == x && tmp.v == v) break;}cal(cnt);}}else low[x] = min(low[x],dfn[v]);if(low[v] > dfn[x]) ans1++; //這句放到dfn[v]==0那里也可以 ，放到這里應該也沒錯！ } } int main() {while(~scanf("%d%d",&n,&m)) {if(n == 0 && m == 0) break;init();for(int u,v,i = 1; i<=m; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 0; i<n; i++) {if(dfn[i] == 0) tarjan(i,-1);//因為題目保證是連通圖所以其實可以直接tarjan(1,-1)的 }printf("%d %d\n",ans1,ans2);}return 0 ; }

AC代碼3：（網上找的一個用set代替cal函數(shù)的版本）傳送門

#include <bits/stdc++.h> using namespace std;const int M = 200010; const int N = 10010;struct Edge {int from, to;int next; } edge[M]; int head[N]; int cnt_edge; void add_edge(int u, int v) {edge[cnt_edge].from = u;edge[cnt_edge].to = v;edge[cnt_edge].next = head[u];head[u] = cnt_edge++; }int dfn[N]; int idx; int low[N]; stack<Edge> stk; set<int> bcc; int cut; // 橋的數(shù)量 int ans; // 沖突邊數(shù)量 int m, n;void dfs(int u, int pre) {dfn[u] = low[u] = ++idx;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (v == pre) continue;if (!dfn[v]){stk.push(edge[i]);dfs(v, u);low[u] = min(low[u], low[v]);if (low[v] >= dfn[u]) // 割點{Edge tmp;int cnt = 0;bcc.clear();do {cnt++;tmp = stk.top();stk.pop();bcc.insert(tmp.from);bcc.insert(tmp.to);} while (tmp.from != u || tmp.to != v);if (cnt > bcc.size()) ans += cnt;}if (low[v] > dfn[u]) ++cut;}else if (dfn[v] < dfn[u]){stk.push(edge[i]);low[u] = min(low[u], dfn[v]);}} }void init() {memset(head, -1, sizeof head);memset(dfn, 0, sizeof dfn);ans = cut = cnt_edge = idx = 0; }int main() {while (~scanf("%d%d", &n, &m)){if (n == 0 && m == 0) break;int u, v;init();for (int i = 0; i < m; ++i){scanf("%d%d", &u, &v);add_edge(u, v);add_edge(v, u);}for (int i = 1; i <= n; ++i)if (!dfn[i]) dfs(i, -1);printf("%d %d\n", cut, ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的【HDU - 3394】Railway（点双连通分量，Tarjan算法，思维tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。