fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 105;
  5. vector<int> adj[MAXN];  // Danh sách kề
  6. bool visited[MAXN];
  7. int parent[MAXN];       // Lưu đỉnh cha trong DFS
  8. vector<pair<int, int>> directedEdges; // Danh sách cạnh có hướng
  9. int n, m, t;
  10.  
  11. // DFS kiểm tra liên thông mạnh
  12. void dfs(int u) {
  13.     visited[u] = true;
  14.     for (int v : adj[u]) {
  15.         if (!visited[v]) dfs(v);
  16.     }
  17. }
  18.  
  19. // Kiểm tra đồ thị có định chiều được không
  20. bool isStronglyOrientable() {
  21.     // Kiểm tra liên thông
  22.     fill(visited, visited + n + 1, false);
  23.     dfs(1);
  24.     if (count(visited + 1, visited + n + 1, true) != n) return false;
  25.  
  26.     // Kiểm tra liên thông trên đồ thị ngược
  27.     vector<int> reverseAdj[MAXN];
  28.     for (int u = 1; u <= n; u++) {
  29.         for (int v : adj[u]) {
  30.             reverseAdj[v].push_back(u);
  31.         }
  32.     }
  33.     fill(visited, visited + n + 1, false);
  34.     swap(adj, reverseAdj);
  35.     dfs(1);
  36.     swap(adj, reverseAdj);
  37.     return count(visited + 1, visited + n + 1, true) == n;
  38. }
  39.  
  40. // Định chiều đồ thị sử dụng DFS
  41. void orientGraph(int u) {
  42.     visited[u] = true;
  43.     for (int v : adj[u]) {
  44.         if (!visited[v]) {
  45.             parent[v] = u;
  46.             directedEdges.emplace_back(u, v);
  47.             orientGraph(v);
  48.         } else if (parent[u] != v) {
  49.             directedEdges.emplace_back(u, v); // Chọn hướng còn lại
  50.         }
  51.     }
  52. }
  53.  
  54. int main() {
  55.     cin >> t >> n >> m;
  56.     vector<pair<int, int>> edges(m);
  57.     for (int i = 0; i < m; i++) {
  58.         int u, v;
  59.         cin >> u >> v;
  60.         adj[u].push_back(v);
  61.         adj[v].push_back(u);
  62.         edges[i] = {u, v};
  63.     }
  64.  
  65.     if (t == 1) {
  66.         cout << (isStronglyOrientable() ? 1 : 0) << endl;
  67.     } else if (t == 2) {
  68.         fill(visited, visited + n + 1, false);
  69.         fill(parent, parent + n + 1, -1);
  70.         orientGraph(1);
  71.         sort(directedEdges.begin(), directedEdges.end());
  72.  
  73.         cout << n << " " << m << endl;
  74.         for (auto [u, v] : directedEdges) {
  75.             cout << u << " " << v << endl;
  76.         }
  77.     }
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5276KB
comments ()
stdin 
1
4 5
1 2
1 3
1 4
2 4
3 4
stdout 
1
https://ideone.com/RPuaiz
language:
C++ (gcc 8.3)
created:
5 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!