fork(1) 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. }
Runtime error #stdin #stdout #stderr 0.64s 528896KB
comments (?)
stdin
copy 
100 485
1 6 69
1 9 39
1 17 29
1 27 75
1 31 68
1 37 12
1 38 77
1 39 39
1 44 80
1 62 82
1 70 73
1 96 19
2 5 71
2 6 81
2 10 98
2 32 42
2 34 22
2 60 49
2 73 52
2 75 4
2 86 43
2 90 13
3 24 67
3 31 27
3 42 57
3 44 41
3 57 50
3 76 50
3 81 31
3 93 6
3 98 96
3 99 62
3 100 43
4 13 9
4 29 37
4 35 45
4 38 90
4 46 61
4 58 92
4 86 84
4 96 54
5 7 54
5 14 38
5 22 99
5 35 72
5 40 80
5 79 77
6 7 99
6 18 58
6 29 13
6 31 74
6 37 29
6 52 80
6 56 28
6 58 1
6 62 13
6 65 75
6 66 36
6 76 15
6 81 58
6 97 11
7 10 45
7 14 67
7 33 66
7 36 22
7 56 59
7 58 41
7 59 12
7 60 74
7 67 54
7 74 92
8 18 76
8 26 26
8 37 33
8 61 7
8 67 44
8 68 6
8 93 100
9 10 56
9 15 98
9 45 65
9 59 70
9 73 100
10 26 9
10 78 52
10 81 59
11 26 90
11 36 31
11 44 76
11 53 39
11 86 96
12 14 26
12 23 53
12 44 5
12 49 17
12 51 70
12 52 26
12 54 36
12 92 71
13 15 36
13 22 25
13 23 78
13 24 21
13 37 40
13 41 30
13 63 21
13 65 60
13 77 89
13 81 84
14 17 30
14 19 18
14 35 23
14 44 48
14 51 27
14 53 20
14 63 90
14 78 1
14 81 13
14 92 33
14 98 55
14 99 34
15 21 44
15 27 50
15 31 55
15 40 89
15 62 71
15 87 58
15 92 80
15 93 32
15 96 69
16 28 53
16 38 47
16 40 15
16 44 29
16 49 32
16 63 17
16 82 100
16 92 68
17 26 43
17 27 4
17 42 100
17 63 20
17 64 72
17 91 30
17 93 1
18 26 36
18 53 25
18 55 60
18 75 32
18 98 5
19 32 93
19 39 18
19 44 70
19 49 71
19 52 36
19 60 92
19 67 66
19 69 72
19 84 17
19 90 58
19 91 86
20 22 46
20 40 1
20 47 49
20 51 60
20 57 57
20 62 46
20 63 21
20 65 21
20 73 3
20 76 8
20 81 59
21 39 11
21 56 36
21 65 95
21 67 5
22 24 58
22 40 18
22 50 51
22 53 83
22 57 57
22 60 90
22 70 11
22 84 85
22 95 58
23 29 1
23 39 75
23 45 21
23 52 4
23 69 31
23 76 22
23 82 73
23 86 27
23 89 60
23 90 64
24 26 66
24 27 28
24 68 60
24 73 78
25 31 23
25 33 35
25 36 34
25 38 31
25 42 58
25 44 41
25 48 87
25 56 97
25 62 34
25 78 47
25 88 14
25 94 23
25 95 81
25 96 97
26 30 10
26 31 88
26 41 10
26 56 92
26 67 28
26 83 93
27 36 17
27 37 66
27 39 24
27 43 85
27 46 72
27 55 73
27 56 20
27 58 1
27 72 66
27 85 3
27 87 72
27 90 20
27 94 13
27 100 41
28 38 47
28 54 93
28 65 11
28 72 58
28 86 30
28 88 79
29 32 76
29 35 49
29 36 93
29 37 82
29 53 62
29 77 81
30 33 47
30 52 48
30 55 84
30 74 97
30 76 35
30 98 71
31 55 60
31 72 74
31 79 27
31 85 2
31 86 25
32 36 79
32 37 9
32 38 57
32 65 76
32 67 33
32 76 28
32 87 79
32 88 23
32 93 31
32 99 53
32 100 10
33 37 34
33 38 94
33 42 88
33 54 39
33 62 87
33 66 91
33 70 47
33 79 42
34 63 73
34 64 37
34 68 23
34 91 68
34 96 97
35 37 76
35 50 88
35 51 62
35 78 82
35 80 44
35 88 41
36 45 38
36 55 58
36 57 18
36 74 83
36 76 71
36 80 80
37 41 98
37 53 39
37 57 51
37 61 66
37 72 40
37 74 60
38 48 34
38 49 28
38 52 100
38 57 46
38 60 35
38 74 25
38 78 34
38 95 18
39 57 49
39 66 32
39 70 63
39 84 96
39 88 79
40 44 26
40 48 3
40 51 63
40 52 67
40 54 46
40 65 25
40 74 25
40 86 70
40 90 71
40 92 96
41 52 66
41 54 36
41 55 28
41 57 98
41 64 67
41 66 22
41 87 60
41 96 31
42 50 26
42 53 46
42 81 1
43 53 92
43 66 43
44 51 90
44 59 8
44 71 41
44 73 26
44 88 38
45 52 6
45 75 68
45 95 38
46 53 84
46 59 59
46 73 40
46 77 52
46 88 5
46 97 56
47 51 64
47 56 53
47 62 42
47 100 37
48 50 50
48 61 82
48 63 18
48 66 32
48 72 92
48 86 96
48 91 43
48 99 60
49 51 94
49 60 81
49 62 19
49 70 38
49 79 55
49 95 97
49 98 11
50 54 1
50 55 11
50 60 16
50 64 72
50 76 92
50 83 82
50 95 35
51 55 10
51 69 62
52 54 86
52 55 40
52 93 60
53 54 8
53 59 38
53 87 54
53 96 65
53 97 37
53 98 28
54 89 21
55 84 73
56 69 81
56 86 89
56 88 2
57 73 93
57 75 22
57 76 47
57 82 19
57 86 72
57 98 62
58 61 10
58 80 25
58 89 60
58 90 85
58 93 7
59 60 78
59 63 94
59 69 69
59 87 28
60 64 95
60 73 58
60 77 93
60 91 85
60 93 66
60 99 49
61 74 94
61 85 53
63 68 31
63 71 93
63 74 52
63 78 86
63 86 20
63 96 13
64 70 3
64 77 65
64 92 37
65 68 23
65 73 52
65 93 95
65 96 8
65 100 20
66 76 69
66 78 28
66 85 67
66 94 76
66 97 96
67 70 73
67 80 24
67 97 99
68 90 31
68 98 37
69 72 68
69 75 57
69 82 23
69 89 80
69 90 77
69 91 15
69 94 67
69 96 35
70 87 45
70 97 62
71 94 84
72 73 95
72 77 82
72 81 68
72 88 11
72 91 65
73 84 51
74 90 100
75 83 16
75 88 2
75 96 6
75 98 59
76 89 36
77 81 45
77 86 99
77 98 44
77 99 93
79 90 83
80 81 60
80 85 40
80 91 15
82 84 65
82 92 29
82 100 14
84 89 52
85 88 79
85 92 82
85 96 23
86 91 58
86 100 39
87 99 11
88 90 60
90 91 17
92 96 71
92 100 97
93 100 53
94 95 91
96 100 49
-1
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/CKuotJ
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!