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 
98 146
1 2 1
2 3 300
3 4 1
4 5 300
5 6 1
6 7 300
7 8 1
8 9 300
9 10 1
10 11 300
11 12 1
12 13 300
13 14 1
14 15 300
15 16 1
16 17 300
17 18 1
18 19 300
19 20 1
20 21 300
21 22 1
22 23 300
23 24 1
24 25 300
25 26 1
26 27 300
27 28 1
28 29 300
29 30 1
30 31 300
31 32 1
32 33 300
33 34 1
34 35 300
35 36 1
36 37 300
37 38 1
38 39 300
39 40 1
40 41 300
41 42 1
42 43 300
43 44 1
44 45 300
45 46 1
46 47 300
47 48 1
48 49 300
50 51 300
51 52 1
52 53 300
53 54 1
54 55 300
55 56 1
56 57 300
57 58 1
58 59 300
59 60 1
60 61 300
61 62 1
62 63 300
63 64 1
64 65 300
65 66 1
66 67 300
67 68 1
68 69 300
69 70 1
70 71 300
71 72 1
72 73 300
73 74 1
74 75 300
75 76 1
76 77 300
77 78 1
78 79 300
79 80 1
80 81 300
81 82 1
82 83 300
83 84 1
84 85 300
85 86 1
86 87 300
87 88 1
88 89 300
89 90 1
90 91 300
91 92 1
92 93 300
93 94 1
94 95 300
95 96 1
96 97 300
97 98 1
1 50 5
2 51 5
3 52 5
4 53 5
5 54 5
6 55 5
7 56 5
8 57 5
9 58 5
10 59 5
11 60 5
12 61 5
13 62 5
14 63 5
15 64 5
16 65 5
17 66 5
18 67 5
19 68 5
20 69 5
21 70 5
22 71 5
23 72 5
24 73 5
25 74 5
26 75 5
27 76 5
28 77 5
29 78 5
30 79 5
31 80 5
32 81 5
33 82 5
34 83 5
35 84 5
36 85 5
37 86 5
38 87 5
39 88 5
40 89 5
41 90 5
42 91 5
43 92 5
44 93 5
45 94 5
46 95 5
47 96 5
48 97 5
49 98 5
50 49 3
-1
stdout
copy 
2 51 52 3 4 53 54 5 6 55 56 7 8 57 58 9 10 59 60 11 12 61 62 13 14 63 64 15 16 65 66 17 18 67 68 19 20 69 70 21 22 71 72 23 24 73 74 25 26 75 76 27 28 77 78 29 30 79 80 31 32 81 82 33 34 83 84 35 36 85 86 37 38 87 88 39 40 89 90 41 42 91 92 43 44 93 94 45 46 95 96 47 48 97 98 49 50 1
https://ideone.com/8EuKLK
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!