fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. static const int MAXN = 100000;
  5. static const int MAXM = 300000;
  6.  
  7. int n, m;
  8. vector<pair<int,int>> adj[MAXN+1]; // (neighbor, edge_id)
  9. int tin[MAXN+1], low[MAXN+1], timer = 1;
  10. bool isBridge[MAXM];
  11. bool used_edge[MAXM];
  12. bool vis[MAXN+1];
  13. pair<int,int> answer[MAXM];
  14.  
  15. // 1) Find all bridges
  16. void dfsBridge(int u, int pe) {
  17.     tin[u] = low[u] = timer++;
  18.     for (auto &pr : adj[u]) {
  19.         int v = pr.first, id = pr.second;
  20.         if (id == pe) continue;
  21.         if (!tin[v]) {
  22.             dfsBridge(v, id);
  23.             low[u] = min(low[u], low[v]);
  24.             if (low[v] > tin[u]) {
  25.                 isBridge[id] = true;
  26.             }
  27.         } else {
  28.             low[u] = min(low[u], tin[v]);
  29.         }
  30.     }
  31. }
  32.  
  33. // 2) Orient every edge in a single DFS
  34. void dfsOrient(int u) {
  35.     vis[u] = true;
  36.     for (auto &pr : adj[u]) {
  37.         int v = pr.first, id = pr.second;
  38.         if (used_edge[id]) continue;
  39.         used_edge[id] = true;
  40.         // orient u -> v
  41.         answer[id] = {u, v};
  42.         if (!vis[v]) {
  43.             dfsOrient(v);
  44.         }
  45.     }
  46. }
  47.  
  48. int main(){
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.  
  52.     cin >> n >> m;
  53.     for(int i = 0; i < m; i++){
  54.         int a, b;
  55.         cin >> a >> b;
  56.         adj[a].emplace_back(b,i);
  57.         adj[b].emplace_back(a,i);
  58.     }
  59.     // 1) Bridge‐find
  60.     dfsBridge(1, -1);
  61.  
  62.     // 2) If any bridge, no strongly‐connected orientation exists
  63.     for(int id = 0; id < m; id++){
  64.         if(isBridge[id]){
  65.             cout << 0 << "\n";
  66.             return 0;
  67.         }
  68.     }
  69.  
  70.     // 3) Orient all edges
  71.     dfsOrient(1);
  72.  
  73.     // 4) Output all m oriented edges
  74.     //    in input order (edge IDs 0..m-1)
  75.     for(int id = 0; id < m; id++){
  76.         cout << answer[id].first
  77.              << " " 
  78.              << answer[id].second
  79.              << "\n";
  80.     }
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 7504KB
comments (?)
stdin
copy 
6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5
stdout
copy 
1 2
2 3
3 1
5 4
4 6
6 5
4 2
3 5
https://ideone.com/UeXxir
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!