CCF 201509-4 高速公路 || Tarjan演算法

來自專欄如何快速高效學習C++？- 計算機軟體能力認證考試系統?

118.190.20.162

試題編號：201509-4

試題名稱：高速公路

時間限制：1.0s

內存限制：256.0MB

問題描述：

問題描述

　　某國有n個城市，為了使得城市間的交通更便利，該國國王打算在城市之間修一些高速公路，由於經費限制，國王打算第一階段先在部分城市之間修一些單向的高速公路。

　　現在，大臣們幫國王擬了一個修高速公路的計劃。看了計劃後，國王發現，有些城市之間可以通過高速公路直接（不經過其他城市）或間接（經過一個或多個其他城市）到達，而有的卻不能。如果城市A可以通過高速公路到達城市B，而且城市B也可以通過高速公路到達城市A，則這兩個城市被稱為便利城市對。　　國王想知道，在大臣們給他的計劃中，有多少個便利城市對。

輸入格式

　　輸入的第一行包含兩個整數n, m，分別表示城市和單向高速公路的數量。

　　接下來m行，每行兩個整數a, b，表示城市a有一條單向的高速公路連向城市b。

輸出格式

　　輸出一行，包含一個整數，表示便利城市對的數量。

樣例輸入

5 5

1 22 33 44 23 5

樣例輸出

樣例說明

　　城市間的連接如圖所示。有3個便利城市對，它們分別是(2, 3), (2, 4), (3, 4)，請注意(2, 3)和(3, 2)看成同一個便利城市對。

評測用例規模與約定

　　前30%的評測用例滿足1 ≤ n ≤ 100, 1 ≤ m ≤ 1000；

　　前60%的評測用例滿足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000；　　所有評測用例滿足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。

得分：60

#include <iostream>#include <vector>#if(__cplusplus==201103L)#include <unordered_map>#include <unordered_set>#else#include <tr1/unordered_map>#include <tr1/unordered_set>namespace std{ using std::tr1::unordered_map; using std::tr1::unordered_set;}#endif#define test 0#define um unordered_map#define us unordered_setusing namespace std;vector<us<int> >cnct;vector<vector<int> >g;vector<int>mark;void dfs(int now,int src){ mark[now]=1; if(now!=src)cnct[src].insert(now); for(int i=0;i<(int)g[now].size();i++){ int next=g[now][i]; if(0==mark[next]){ dfs(next,src); } }}int main(){ int n=0,m=0; cin>>n>>m; g.resize(n+1); for(int i=0;i<m;i++){ int a,b; cin>>a>>b; g[a].push_back(b); } mark.resize(n+1); cnct.resize(n+1); for(int i=1;i<=n;i++){ fill(mark.begin(),mark.end(),0); dfs(i,i); } int res=0; for(int i=1;i<=n;i++){ for(us<int>::iterator it=cnct[i].begin();it!=cnct[i].end();it++){ int next=*it; us<int>::iterator find=cnct[next].find(i); if(find!=cnct[next].end()){ ++res; cnct[next].erase(find); } } } cout<<res<<endl; return 0;}

得分：100

參考鏈接：

ccf 高速公路(連通子圖) - CSDN博客

圖論 SCC（CCF高速公路） - CSDN博客

ccf 高速公路(連通子圖) - CSDN博客

#include <cstdio>#include <cstring>#include <stack>#include <vector>#include <algorithm>//#define LOCALusing namespace std;//鄰接表版本的代碼 vector實現const int N=10005;int n; //圖結點個數int DFN[N];int LOW[N];int time; //訪問時序stack<int> s; //DFS棧vector<int> G[N];int vis[N]; //訪問數組int instack[N]; //是否在棧裏int result;void tarjan(int u){ DFN[u]=LOW[u]=++time; //time從1開始 s.push(u); instack[u]=1; vis[u]=1; for(int j=0;j<G[u].size();j++){ int v=G[u][j]; if(vis[v]==0){ tarjan(v); LOW[u]=min(LOW[u],LOW[v]); } else if(instack[v]){ LOW[u]=min(LOW[u],DFN[v]); } } int m; int cnt=0; //連通分量內部的節點數 if(DFN[u]==LOW[u]){ do{ m=s.top(); instack[m]=0; s.pop(); cnt++; } while(m!=u); if(cnt>1){ result+=cnt*(cnt-1)/2; //考慮多個連通分量的情況 } }}int main(){ #ifdef LOCAL freopen("input.txt","r",stdin); #endif // LOCAL int m; //邊數 while(scanf("%d %d",&n,&m)!=EOF){ while(s.size()!=0){ s.pop(); } result=0; //最終結果 time=0; memset(vis,0,sizeof(vis)); //清空vector比清空struct需要時間少很多 memset(G,0,sizeof(G)); memset(DFN,0,sizeof(DFN)); memset(LOW,0,sizeof(LOW)); memset(instack,0,sizeof(instack)); for(int i=0;i<m;i++){ int a,b; scanf("%d %d",&a,&b); G[a].push_back(b); } for(int i=1;i<=n;i++){ if(vis[i]==0){ vis[i]=1; tarjan(i); } } printf("%d ",result); } return 0;}