fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr int MIL = 1'000'000;
  5.  
  6. // Funkcje pomocnicze do mapowania indeksów
  7. inline int edgeNode(int idx) { return idx; }
  8. inline int prefixNode(int idx) { return MIL + idx; }
  9. inline int suffixNode(int idx) { return 2 * MIL + idx; }
  10.  
  11. // Klasa do wykrywania cyklu w grafie skierowanym
  12. struct CycleDetector {
  13.     vector<vector<int>>& graph;
  14.     vector<bool> visited, recStack;
  15.  
  16.     CycleDetector(vector<vector<int>>& g) : graph(g) {
  17.         visited.assign(graph.size(), false);
  18.         recStack.assign(graph.size(), false);
  19.     }
  20.  
  21.     bool dfs(int u) {
  22.         visited[u] = true;
  23.         recStack[u] = true;
  24.         for (int v : graph[u]) {
  25.             if (!visited[v] && dfs(v)) return true;
  26.             else if (recStack[v]) return true;
  27.         }
  28.         recStack[u] = false;
  29.         return false;
  30.     }
  31.  
  32.     bool hasCycle() {
  33.         for (int i = 0; i < (int)graph.size(); i++)
  34.             if (!visited[i] && dfs(i))
  35.                 return true;
  36.         return false;
  37.     }
  38. };
  39.  
  40. // Funkcja budująca graf na podstawie wczytanych danych
  41. void buildGraph(int n, int m,
  42.                 const vector<vector<pair<int,int>>>& in,
  43.                 const vector<vector<pair<int,int>>>& out,
  44.                 vector<vector<int>>& graf) {
  45.     // Dodajemy krawędzie prefixowe i suffixowe
  46.     for (int i = 1; i <= n; ++i) {
  47.         graf[prefixNode(i)].push_back(edgeNode(i));
  48.         graf[suffixNode(i)].push_back(edgeNode(i));
  49.     }
  50.  
  51.     for (int i = 1; i <= n; ++i) {
  52.         for (int j = 0; j + 1 < (int)out[i].size(); ++j) {
  53.             graf[prefixNode(out[i][j].second)].push_back(prefixNode(out[i][j + 1].second));
  54.             graf[suffixNode(out[i][j + 1].second)].push_back(suffixNode(out[i][j].second));
  55.         }
  56.     }
  57.  
  58.     for (int i = 1; i <= n; ++i) {
  59.         int l = 0;
  60.         for (int j = 0; j < (int)in[i].size(); ++j) {
  61.             if (out[i].empty()) continue;
  62.  
  63.             while (l < (int)out[i].size() && out[i][l].first < in[i][j].first) l++;
  64.             if (l == (int)out[i].size()) continue;
  65.  
  66.             if (out[i][l].first == in[i][j].first) {
  67.                 int p = l;
  68.                 while (p + 1 < (int)out[i].size() && out[i][p + 1].first == in[i][j].first) p++;
  69.  
  70.                 if (l > 0)
  71.                     graf[in[i][j].second].push_back(suffixNode(out[i][l - 1].second));
  72.                 if (p + 1 < (int)out[i].size())
  73.                     graf[in[i][j].second].push_back(prefixNode(out[i][p + 1].second));
  74.             } else {
  75.                 graf[in[i][j].second].push_back(prefixNode(out[i][0].second));
  76.             }
  77.         }
  78.     }
  79. }
  80.  
  81. // Główna funkcja rozwiązująca pojedynczy test
  82. void solve() {
  83.     vector<vector<pair<int,int>>> in(MIL + 1), out(MIL + 1);
  84.     int n, m;
  85.     cin >> n >> m;
  86.  
  87.     for (int i = 0; i < m; ++i) {
  88.         int a, b, c; cin >> a >> b >> c;
  89.         out[a].emplace_back(c, i);
  90.         in[b].emplace_back(c, i);
  91.     }
  92.  
  93.     for (int i = 1; i <= n; ++i) {
  94.         sort(in[i].begin(), in[i].end());
  95.         sort(out[i].begin(), out[i].end());
  96.     }
  97.  
  98.     int maxNode = max({m - 1, prefixNode(n), suffixNode(n)});
  99.     vector<vector<int>> graf(maxNode + 1);
  100.  
  101.     buildGraph(n, m, in, out, graf);
  102.  
  103.     CycleDetector cd(graf);
  104.     cout << (cd.hasCycle() ? "Cycle detected\n" : "No cycle\n");
  105. }
  106.  
  107. int main() {
  108.     ios::sync_with_stdio(false);
  109.     cin.tie(nullptr);
  110.  
  111.     int t; cin >> t;
  112.     while (t--) solve();
  113.  
  114.     return 0;
  115. }
  116.  
Success #stdin #stdout 0.17s 97684KB
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 cycle
No cycle
No cycle
No cycle
No cycle
https://ideone.com/sbNFuq
language:
C++14 (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!