fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(x) (x).begin(),(x).end()
  5. #define sz(x) ((int)(x).size())
  6. typedef vector<int> VI;
  7.  
  8. const int N = 100;
  9.  
  10. struct edge {
  11.     int from, to, cost;
  12. };
  13.  
  14. VI parent, DSUparent, DSUrank, colour; //parent, colour для DFS. Остальное для disjoint-set
  15. vector <edge> edges, result;           //в result входят все вершины, которые досягаемы из цикла с наименьшим весом
  16. vector <VI> graph (N, VI(0));          // adjacency list
  17. vector < vector <bool> > visited (N, vector <bool>(N)); // Хранятся использованные рёбра
  18. int cycle_end, cycle_st;               // конец и начало цикла, которые найдены DFS
  19. int n, m;                              // для чтения задачи
  20. bool foundCycle;
  21.                        // 
  22. // disjoint-set 
  23. int findSet (int v) {
  24.     return (v == DSUparent[v]) ? v : (DSUparent[v] = findSet (DSUparent[v]));
  25. }
  26. inline void makeSet (int a) {
  27.     DSUrank[a] = 0;
  28.     DSUparent[a] = a;
  29. }
  30. void unionSet (int a, int b) {
  31.     a = findSet(a);
  32.     b = findSet(b);
  33.  
  34.     if (a == b) {
  35.         return;
  36.     }
  37.     if (DSUrank[a] > DSUrank[b]) {
  38.         DSUparent[b] = a;
  39.     } else {
  40.         DSUparent[a] = b;
  41.         if (DSUrank[a] == DSUrank[b]) {
  42.             DSUrank[b] = DSUrank[b] + 1;
  43.         }
  44.     }
  45. }
  46. //жадный алгоритм, который находит все вершины, которые можно найти из цикла с 
  47. // наименьшим весом. Принцип работы как у алгоритма Крускала.
  48.  
  49. bool kruskal (vector <edge> e) {
  50.     bool done = false;
  51.  
  52.     for (auto i : e) {
  53.         int from = i.from, to = i.to;
  54.         if (findSet (to) == findSet (from) && !visited[from][to] && !visited[to][from]) {
  55.             done = true;
  56.         }
  57.         if (!visited[from][to] && !visited[to][from]) {
  58.             result.push_back (i);
  59.             unionSet (from, to);
  60.             visited[from][to] = true;
  61.             visited[to][from] = true;
  62.             if (done) {
  63.                 return true;
  64.             }
  65.         }
  66.     }
  67.     return false;
  68. }
  69. //DFS, который находит цикл.
  70. int dfs (int v) {
  71.     colour[v] = 1;
  72.     for (auto u : graph[v]) {
  73.         if (colour[u] == 0)  {
  74.             parent[u] = v;
  75.             dfs (u);
  76.         } else if (colour[u] == 1 && parent[v] != u) {
  77.             parent[u] = v;
  78.             cycle_end = v;
  79.             cycle_st = u;
  80.             return 0;
  81.         }
  82.     }
  83.     colour[v] = 2;
  84.     return 0;
  85. }
  86. // чтение графа
  87. void readData () {
  88.     for (auto& v : visited) {
  89.         v.assign(N, false);
  90.     }
  91.     edges.clear();
  92.     parent.clear();
  93.     DSUrank.clear();
  94.     DSUparent.clear();
  95.     colour.clear();
  96.     result.clear();
  97.     result.resize(0);
  98.     edges.resize(m);
  99.     parent.resize(n);
  100.     DSUrank.resize(n);
  101.     DSUparent.resize(n);
  102.     colour.resize(n);
  103.     // непосредственное чтение
  104.     for (int i = 0; i < m; i++) {
  105.         int x, y, z;
  106.         scanf ("%d %d %d", &x, &y, &z);
  107.         x--; y--;
  108.         edges[i] = {x, y, z};
  109.     }
  110.     // сортируем все рёбра в порядке возрастания веса
  111.     sort (all(edges), [](auto a, auto b) {return a.cost < b.cost;});
  112.     // для disjoint-set
  113.     for (int i = 0; i < n; i++) {
  114.         makeSet (i);
  115.     }
  116.     //наличие цикла, а также записывание "наименьшего цикла" в 
  117.     // vector <edge> result
  118.     foundCycle = kruskal (edges);
  119. }
  120. void solve () {
  121.  
  122.     if (foundCycle) {
  123.         for (auto& v : graph) {
  124.             v.resize(0);
  125.             v.shrink_to_fit();
  126.         }
  127.         // на основе vector <edge> result
  128.         // конструируем граф
  129.         for (auto i : result) {
  130.             graph[i.from].push_back (i.to);
  131.             graph[i.to].push_back (i.from);
  132.         }
  133.  
  134.         colour.assign (n, 0);
  135.         parent.assign (n, -1);
  136.  
  137.         for (int j = 0; j < n; j++) {
  138.             if (colour[j] == 0) {
  139.                 dfs(j);
  140.             }
  141.         }
  142.  
  143.         vector<int> cycle;
  144.  
  145.         cycle.push_back (cycle_st);
  146.  
  147.         for (int v=cycle_end; v!=cycle_st; v=parent[v]) {
  148.             cycle.push_back (v);
  149.         }
  150.  
  151.         reverse (all(cycle));
  152.  
  153.         for (auto k : cycle) {
  154.             printf ("%d ", k + 1);
  155.         }
  156.  
  157.         foundCycle = false;
  158.         printf ("\n");
  159.  
  160.     } else {
  161.         cout << "No solution." <<"";
  162.         printf ("\n");
  163.     }
  164. }
  165.  
  166. int main() {
  167.     int count = 6;
  168.     while (count > 1) {
  169.         scanf ("%d", &n);
  170.         if (n < 0) {
  171.             break;
  172.         } else {
  173.             scanf ("%d", &m);
  174.             readData();
  175.             solve();
  176.             count--;
  177.         }
  178.     }
  179.     return 0;
  180. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1
stdout
copy 
3 5 2 1 
No solution.
https://ideone.com/O2qb8f
language:
C++14 (gcc 8.3)
created:
8 years 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!