fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_M = 1000005;
  5. const int MAX_G = 3000005;
  6.  
  7. vector<pair<int, int>> in[MAX_M], out[MAX_M];
  8. vector<int> graf[MAX_G];
  9. bool odw[MAX_G], ter[MAX_G];
  10. vector<int> stak, cykl;
  11. bool czy = false;
  12. int wie = -1;
  13.  
  14. int from[MAX_M], to[MAX_M], attr[MAX_M];
  15.  
  16. void dfs(int x)
  17. {
  18.     if (wie != -1) return;
  19.     odw[x] = true;
  20.     ter[x] = true;
  21.     stak.push_back(x);
  22.  
  23.     for (int i : graf[x])
  24.     {
  25.         if (ter[i] && wie == -1)
  26.         {
  27.             czy = true;
  28.             wie = i;
  29.             while (stak.back() != wie)
  30.             {
  31.                 cykl.push_back(stak.back());
  32.                 stak.pop_back();
  33.             }
  34.             cykl.push_back(stak.back());
  35.             stak.pop_back();
  36.             return;
  37.         }
  38.         if (!odw[i])
  39.         {
  40.             dfs(i);
  41.         }
  42.     }
  43.     stak.pop_back();
  44.     ter[x] = false;
  45. }
  46.  
  47. void solve()
  48. {
  49.     stak.clear();
  50.     cykl.clear();
  51.     int mil = 1000000;
  52.  
  53.     int n, m, a, b, c;
  54.     cin >> n >> m;
  55.  
  56.     for (int i = 0; i <= n; ++i)
  57.     {
  58.         in[i].clear();
  59.         out[i].clear();
  60.     }
  61.     for (int i = 0; i < 3 * mil; ++i)
  62.     {
  63.         graf[i].clear();
  64.         odw[i] = false;
  65.         ter[i] = false;
  66.     }
  67.  
  68.     for (int i = 0; i < m; ++i)
  69.     {
  70.         cin >> a >> b >> c;
  71.         from[i] = a;
  72.         to[i] = b;
  73.         attr[i] = c;
  74.         out[a].push_back({c, i});
  75.         in[b].push_back({c, i});
  76.     }
  77.  
  78.     for (int i = 0; i < m; ++i)
  79.     {
  80.         graf[mil + i].push_back(i);
  81.         graf[2 * mil + i].push_back(i);
  82.     }
  83.  
  84.     for (int i = 1; i <= n; ++i)
  85.     {
  86.         sort(in[i].begin(), in[i].end());
  87.         sort(out[i].begin(), out[i].end());
  88.  
  89.         for (int j = 0; j < (int)out[i].size() - 1; ++j)
  90.         {
  91.             graf[mil + out[i][j].second].push_back(mil + out[i][j + 1].second);
  92.             graf[2 * mil + out[i][j + 1].second].push_back(2 * mil + out[i][j].second);
  93.         }
  94.     }
  95.  
  96.     for (int i = 1; i <= n; ++i)
  97.     {
  98.         int l = 0, p = 0;
  99.         for (int j = 0; j < (int)in[i].size(); ++j)
  100.         {
  101.             int walk_in = in[i][j].second;
  102.             if ((int)out[i].size() == 0) continue;
  103.  
  104.             while (l < (int)out[i].size() && out[i][l].first < in[i][j].first)
  105.                 ++l;
  106.  
  107.             if (l < (int)out[i].size() && out[i][l].first == in[i][j].first)
  108.             {
  109.                 p = l;
  110.                 while (p + 1 < (int)out[i].size() && out[i][p + 1].first == in[i][j].first)
  111.                     ++p;
  112.  
  113.                 if (l > 0)
  114.                 {
  115.                     int walk_out = out[i][l - 1].second;
  116.                     if (to[walk_in] == from[walk_out] && attr[walk_in] != attr[walk_out])
  117.                         graf[walk_in].push_back(2 * mil + walk_out);
  118.                 }
  119.                 if (p + 1 < (int)out[i].size())
  120.                 {
  121.                     int walk_out = out[i][p + 1].second;
  122.                     if (to[walk_in] == from[walk_out] && attr[walk_in] != attr[walk_out])
  123.                         graf[walk_in].push_back(mil + walk_out);
  124.                 }
  125.             }
  126.             else
  127.             {
  128.                 int walk_out = out[i][0].second;
  129.                 if (to[walk_in] == from[walk_out] && attr[walk_in] != attr[walk_out])
  130.                     graf[walk_in].push_back(mil + walk_out);
  131.             }
  132.         }
  133.     }
  134.  
  135.     for (int i = 0; i < m; ++i)
  136.     {
  137.         if (!odw[i]) dfs(i);
  138.         if (wie != -1)
  139.         {
  140.             cout << "YES\n";
  141.             int count = 0;
  142.             vector<int> res;
  143.             for (int j : cykl)
  144.             {
  145.                 if (j < mil)
  146.                 {
  147.                     ++count;
  148.                     res.push_back(j + 1);
  149.                 }
  150.             }
  151.             cout << count << ' ';
  152.             for (int id : res) cout << id << ' ';
  153.             cout << '\n';
  154.             wie = -1;
  155.             return;
  156.         }
  157.     }
  158.     cout << "NO\n";
  159. }
  160.  
  161. int main()
  162. {
  163.     ios_base::sync_with_stdio(false);
  164.     cin.tie(nullptr);
  165.  
  166.     int t;
  167.     cin >> t;
  168.     while (t--)
  169.     {
  170.         solve();
  171.     }
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0.07s 132728KB
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
2 3 2 
NO
YES
6 6 5 4 3 2 1 
YES
2 3 2
https://ideone.com/SX4iYL
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!