1? ? ? ? ? ? ? ? ?
/*
題意： 給你一個圖，求這個有向圖示否是一個強連通圖（每兩個節點都是可以相互到達的）！
思路1：按正向邊dfs一遍，將經過的節點計數，如果記錄的節點的個數小于n，那么就說明圖按照正向邊就不是連同的，所以就不是強連通圖！
然后按照反向邊再進行另一個dfs，同樣對經過的節點的個數進行計數，如果個數==n則說明正向遍歷和反響遍歷都是連通的！那么整個圖就是強連通的圖！
思路2：直接套用tarjan算法，求出每一個節點所對應的縮點的值， 如果縮點的個數==1，那么證明就會只有一個強連通分量！也就是強連通圖
思路3：多次次調用tarjan算法，判斷low[u]==pre[u]&&u==1, 如果不滿足說明改圖有多個縮點，那就不是強連通圖!下圖說明一下....
*/
//思路一：
2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<vector> 7 #define N 10005 8 using namespace std; 9 10 vector<int>uv[N]; 11 vector<int>vu[N]; 12 13 int vis[N]; 14 15 int cnt; 16 17 int n, m; 18 19 void dfs1(int u){ 20 vis[u]=1; 21 ++cnt; 22 int len=uv[u].size(); 23 for(int i=0; i<len; ++i){ 24 int v=uv[u][i]; 25 if(!vis[v]) 26 dfs1(v); 27 } 28 } 29 30 31 void dfs2(int v){ 32 vis[v]=1; 33 ++cnt; 34 int len=vu[v].size(); 35 for(int i=0; i<len; ++i){ 36 int u=vu[v][i]; 37 if(!vis[u]) 38 dfs2(u); 39 } 40 } 41 42 int main(){ 43 while( scanf("%d%d", &n, &m) && (n||m) ){ 44 memset(vis, 0, sizeof(vis)); 45 for(int i=1; i<=n; ++i){ 46 uv[i].clear(); 47 vu[i].clear(); 48 } 49 while(m--){ 50 int u, v; 51 scanf("%d%d", &u, &v); 52 uv[u].push_back(v); 53 vu[v].push_back(u); 54 } 55 cnt=0; 56 dfs1(1); 57 58 if(cnt==n){ 59 memset(vis, 0, sizeof(vis)); 60 cnt=0; 61 dfs2(1); 62 if(cnt!=n) 63 printf("No\n"); 64 else printf("Yes\n"); 65 } 66 else printf("No\n"); 67 68 } 69 return 0; 70 } 71
//思路二：
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<stack>#define N 10005using namespace std;vector<int>g[N];stack<int>s; int pre[N], low[N];int scc[N];int scc_cnt;int dfs_clock;void tarjans(int u){pre[u]=low[u]=++dfs_clock;s.push(u);int len=g[u].size();for(int i=0; i<len; ++i){int v=g[u][i];if(pre[u]>pre[v]){if(!pre[v]){tarjans(v);low[u]=min(low[v], low[u]); }elselow[u]=min(pre[v], low[u]);} }if(low[u]==pre[u]){++scc_cnt;while(1){int x=s.top();s.pop();scc[x]=scc_cnt;if(x==u) break;}}}int n, m;int main(){while(scanf("%d%d", &n, &m) && (n||m)){while(m--){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v); } dfs_clock=0;scc_cnt=0;for(int i=1; i<=n; ++i)if(!scc[i])tarjans(i);int i;for(i=2; i<=n; ++i)if(scc[i]!=scc[1]){printf("No\n");break;}if(i>n) printf("Yes\n");memset(pre, 0, sizeof(pre));memset(low, 0, sizeof(low));memset(scc, 0, sizeof(scc));for(i=1; i<=n; ++i)g[i].clear();}return 0; }
//思路三：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #define N 10005 7 using namespace std; 8 9 vector<int>g[N]; 10 bool flag; 11 int pre[N], low[N]; 12 int dfs_clock; 13 14 void tarjans(int u){ 15 pre[u]=low[u]=++dfs_clock; 16 int len=g[u].size(); 17 for(int i=0; i<len; ++i){ 18 int v=g[u][i]; 19 if(!flag) return ; 20 if(pre[u]>pre[v]){ 21 if(!pre[v]){ 22 tarjans(v); 23 low[u]=min(low[v], low[u]); 24 } 25 else 26 low[u]=min(pre[v], low[u]); 27 } 28 } 29 30 if(low[u]==pre[u] && u!=1) 31 flag=false; 32 } 33 34 int n, m; 35 int main(){ 36 while(scanf("%d%d", &n, &m) && (n||m)){ 37 while(m--){ 38 int u, v; 39 scanf("%d%d", &u, &v); 40 g[u].push_back(v); 41 } 42 dfs_clock=0; 43 flag=true; 44 for(int i=1; i<=n; ++i) 45 if(!pre[i]){ 46 if(!flag) break; 47 tarjans(i); 48 } 49 50 if(!flag) printf("No\n"); 51 else printf("Yes\n"); 52 memset(pre, 0, sizeof(pre)); 53 memset(low, 0, sizeof(low)); 54 for(int i=1; i<=n; ++i) 55 g[i].clear(); 56 } 57 return 0; 58 } 59
?
?
,怎么處理?)
)
的區別)
)
)
)
)
