fork download
copy 
  1. // CT.CPP
  2. #include <iostream>
  3. #include <vector>
  4. #include <stack>
  5. #include <sstream>
  6. #include <string>
  7. #include <algorithm> // for reverse
  8. using namespace std;
  9.  
  10. const int MAX = 1005;
  11. vector<int> adj[MAX];
  12. int inDeg[MAX], outDeg[MAX];
  13. bool visited[MAX];
  14. int n, start, option;
  15.  
  16. void dfs(int u) {
  17.     visited[u] = true;
  18.     for (int v : adj[u]) {
  19.         if (!visited[v]) dfs(v);
  20.     }
  21. }
  22.  
  23. void dfsUndirected(int u, vector<vector<int>> &undirAdj) {
  24.     visited[u] = true;
  25.     for (int v : undirAdj[u]) {
  26.         if (!visited[v]) dfsUndirected(v, undirAdj);
  27.     }
  28. }
  29.  
  30. bool isWeaklyConnected() {
  31.     vector<vector<int>> undirAdj(n + 1);
  32.     for (int u = 1; u <= n; ++u) {
  33.         for (int v : adj[u]) {
  34.             undirAdj[u].push_back(v);
  35.             undirAdj[v].push_back(u);
  36.         }
  37.     }
  38.     fill(visited, visited + n + 1, false);
  39.     int s = 1;
  40.     while (s <= n && adj[s].empty()) s++;
  41.     if (s > n) return false;
  42.     dfsUndirected(s, undirAdj);
  43.     for (int i = 1; i <= n; ++i) {
  44.         if ((!adj[i].empty() || inDeg[i] > 0) && !visited[i]) return false;
  45.     }
  46.     return true;
  47. }
  48.  
  49. string checkEulerType() {
  50.     if (!isWeaklyConnected()) return "Khong phai do thi Euler hay nua Euler";
  51.     int startNodes = 0, endNodes = 0;
  52.     for (int i = 1; i <= n; ++i) {
  53.         if (outDeg[i] - inDeg[i] == 1) startNodes++;
  54.         else if (inDeg[i] - outDeg[i] == 1) endNodes++;
  55.         else if (inDeg[i] != outDeg[i]) return "Khong phai do thi Euler hay nua Euler";
  56.     }
  57.     if (startNodes == 0 && endNodes == 0)
  58.         return "Do thi Euler";
  59.     else if (startNodes == 1 && endNodes == 1)
  60.         return "Do thi nua Euler";
  61.     else
  62.         return "Khong phai do thi Euler hay nua Euler";
  63. }
  64.  
  65. vector<int> findEulerPath(int u) {
  66.     vector<int> path;
  67.     stack<int> stk;
  68.     stk.push(u);
  69.     vector<vector<int>> tempAdj(MAX);
  70.     for (int i = 1; i <= n; ++i) tempAdj[i] = adj[i];
  71.  
  72.     while (!stk.empty()) {
  73.         int curr = stk.top();
  74.         if (!tempAdj[curr].empty()) {
  75.             int next = tempAdj[curr].back();
  76.             tempAdj[curr].pop_back();
  77.             stk.push(next);
  78.         } else {
  79.             stk.pop();
  80.             path.push_back(curr);
  81.         }
  82.     }
  83.     reverse(path.begin(), path.end());
  84.     return path;
  85. }
  86.  
  87. int main() {
  88.     cin >> option >> start >> n;
  89.     int u, v;
  90.     string line;
  91.     getline(cin, line); // consume leftover newline
  92.  
  93.     while (getline(cin, line) && !line.empty()) {
  94.         istringstream iss(line);
  95.         iss >> u;
  96.         while (iss >> v) {
  97.             adj[u].push_back(v);
  98.             outDeg[u]++;
  99.             inDeg[v]++;
  100.         }
  101.     }
  102.  
  103.     string result = checkEulerType();
  104.  
  105.     if (option == 1) {
  106.         if (result == "Do thi Euler") cout << 0 << endl;
  107.         else if (result == "Do thi nua Euler") cout << 1 << endl;
  108.         else cout << 2 << endl;
  109.     } else if (option == 2 && result == "Do thi Euler") {
  110.         vector<int> cycle = findEulerPath(start);
  111.         for (int i = 0; i < (int)cycle.size(); ++i) {
  112.             cout << cycle[i];
  113.             if (i + 1 < cycle.size()) cout << " ";
  114.         }
  115.         cout << endl;
  116.     }
  117.  
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
4
2 2 4

1 4

1 1

1 3
stdout
copy 
2
https://ideone.com/1VL93n
language:
C++ (gcc 8.3)
created:
8 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!