fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct State {
  5.     int node;
  6.     int lastAttr;
  7.     bool operator==(const State &o) const {
  8.         return node == o.node && lastAttr == o.lastAttr;
  9.     }
  10. };
  11.  
  12. struct StateHash {
  13.     size_t operator()(const State& s) const {
  14.         return ((size_t)s.node << 20) ^ s.lastAttr;
  15.     }
  16. };
  17.  
  18. int n, m;
  19. vector<tuple<int,int,int>> g[1000005]; // node -> (to, attr, id)
  20. unordered_map<State, bool, StateHash> visited;
  21. unordered_map<State, bool, StateHash> onStack;
  22. unordered_map<State, State, StateHash> parent;
  23. vector<int> cycle;
  24.  
  25. bool dfs(State s) {
  26.     visited[s] = true;
  27.     onStack[s] = true;
  28.     int u = s.node;
  29.     int lastA = s.lastAttr;
  30.  
  31.     for (auto &[v, attr, eid] : g[u]) {
  32.         if (attr == lastA) continue; // attraction must differ
  33.  
  34.         State ns = {v, attr};
  35.         if (!visited[ns]) {
  36.             parent[ns] = s;
  37.             if (dfs(ns)) return true;
  38.         } else if (onStack[ns]) {
  39.             // cycle found, reconstruct cycle
  40.             cycle.clear();
  41.             cycle.push_back(eid);
  42.             State cur = s;
  43.             while (!(cur == ns)) {
  44.                 auto p = parent[cur];
  45.                 int from = p.node;
  46.                 int attrUsed = cur.lastAttr;
  47.                 int to = cur.node;
  48.  
  49.                 // find edge id from p.node to cur.node with attraction cur.lastAttr
  50.                 for (auto &[to2, attr2, eid2] : g[from]) {
  51.                     if (to2 == to && attr2 == attrUsed) {
  52.                         cycle.push_back(eid2);
  53.                         break;
  54.                     }
  55.                 }
  56.                 cur = p;
  57.             }
  58.             reverse(cycle.begin(), cycle.end());
  59.             return true;
  60.         }
  61.     }
  62.     onStack[s] = false;
  63.     return false;
  64. }
  65.  
  66. void solve() {
  67.     cin >> n >> m;
  68.     for (int i = 1; i <= n; i++) g[i].clear();
  69.     visited.clear();
  70.     onStack.clear();
  71.     parent.clear();
  72.  
  73.     for (int i = 1; i <= m; i++) {
  74.         int x, y, c; cin >> x >> y >> c;
  75.         g[x].emplace_back(y, c, i);
  76.     }
  77.  
  78.     bool found = false;
  79.     for (int i = 1; i <= n && !found; i++) {
  80.         State start = {i, 0}; // lastAttr = 0 means no last attraction yet
  81.         if (!visited[start]) {
  82.             if (dfs(start)) {
  83.                 found = true;
  84.             }
  85.         }
  86.     }
  87.  
  88.     if (!found) {
  89.         cout << "NO\n";
  90.     } else {
  91.         cout << "YES\n";
  92.        // cout << (int)cycle.size() << "\n";
  93.         for (int id : cycle) cout << id << " ";
  94.         cout << "\n";
  95.     }
  96. }
  97.  
  98. int main() {
  99.     ios::sync_with_stdio(false);
  100.     cin.tie(nullptr);
  101.  
  102.     int t; cin >> t;
  103.     while (t--) {
  104.         solve();
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.02s 27044KB
comments (?)
stdin
copy 
5
3 3
1 2 1
2 3 2
3 1 1
3 3
2 1 1
1 3 3
3 1 2
2 2
1 2 2
1 2 1
5 6
1 2 1
2 3 2
3 1 1
1 4 3
4 5 4
5 1 3
4 4
1 3 4
3 2 1
2 3 2
2 3 2
stdout
copy 
NO
YES
3 2 
NO
YES
2 3 4 5 6 1 
YES
3 2
https://ideone.com/ZZ7M1U
language:
C++14 (gcc 8.3)
created:
9 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!