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