fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<int,int>> in[3000005];
  5. vector<pair<int,int>> out[3000005];
  6. vector<int> graf[3000005];
  7.  
  8. vector<int> visited(3000005, 0);
  9. bool hasCycle = false;
  10.  
  11. void dfs(int u) {
  12.     if (hasCycle) return;
  13.     visited[u] = 1;
  14.     for (int v : graf[u]) {
  15.         if (visited[v] == 0) {
  16.             dfs(v);
  17.         } else if (visited[v] == 1) {
  18.             hasCycle = true;
  19.             return;
  20.         }
  21.     }
  22.     visited[u] = 2;
  23. }
  24.  
  25. int main()
  26. {
  27.     int mil = 1000000;
  28.     int n,m,a,b,c;
  29.     cin >> n >> m;
  30.     for(int i =0;i < m;++i)
  31.     {
  32.         cin >> a >> b >> c;
  33.         out[a].push_back({c,i});
  34.         in[b].push_back({c,i});
  35.     }
  36.     for(int i = 1;i <= n;++i)
  37.     {
  38.         graf[mil+i].push_back(i);
  39.         graf[2*mil+i].push_back(i);
  40.     }
  41.     for(int i = 1;i <= n;++i)
  42.     {
  43.         sort(in[i].begin(),in[i].end());
  44.         sort(out[i].begin(),out[i].end());
  45.         for(int j = 0;j < (int)out[i].size()-1;++j)
  46.         {
  47.             graf[mil+out[i][j].second].push_back(mil+out[i][j+1].second);
  48.             graf[2*mil+out[i][j+1].second].push_back(2*mil+out[i][j].second);
  49.         }
  50.     }
  51.     int l,p;
  52.     for(int i = 1;i <= n;++i)
  53.     {
  54.         l=0,p=0;
  55.         for(int j = 0;j < (int)in[i].size();++j)
  56.         {
  57.             while(l < (int)out[i].size() && out[i][l].first < in[i][j].first)
  58.             {
  59.                 l++;
  60.             }
  61.             if(l < (int)out[i].size() && out[i][l].first == in[i][j].first)
  62.             {
  63.                 p = l;
  64.                 while(p+1 < (int)out[i].size() && out[i][p+1].first == in[i][j].first)
  65.                 {
  66.                     p++;
  67.                 }
  68.                 if(l > 0)
  69.                 {
  70.                     graf[in[i][j].second].push_back(2*mil+out[i][l-1].second);
  71.                 }
  72.                 if(p+1 < (int)out[i].size())
  73.                 {
  74.                     graf[in[i][j].second].push_back(mil+out[i][p+1].second);
  75.                 }
  76.             }
  77.             else if (!out[i].empty())
  78.             {
  79.                 graf[in[i][j].second].push_back(mil+out[i][0].second);
  80.             }
  81.         }
  82.     }
  83.  
  84.     for(int i = 0;i < m;++i)
  85.     {
  86.         cout << i << " :";
  87.         for(int j : graf[i])
  88.         {
  89.             cout << j << ' ';
  90.         }
  91.         cout << endl;
  92.     }
  93.  
  94.     // Cycle detection
  95.     for(int i = 0; i < 3*mil; ++i)
  96.     {
  97.         if (!graf[i].empty() && visited[i] == 0)
  98.         {
  99.             dfs(i);
  100.             if (hasCycle) break;
  101.         }
  102.     }
  103.  
  104.     if (hasCycle)
  105.         cout << "Cycle detected in the graph." << endl;
  106.     else
  107.         cout << "No cycle found in the graph." << endl;
  108. }
  109.  
Success #stdin #stdout 0.07s 225676KB
comments (?)
stdin
copy 
5 6
1 2 1
2 3 2
3 1 1
1 4 3
4 5 4
5 1 3
stdout
copy 
0 :1000001 
1 :1000002 
2 :1000003 
3 :1000004 
4 :1000005 
5 :2000000 
No cycle found in the graph.
https://ideone.com/4CAXDK
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!