fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3.  
  4. #define int long long
  5.  
  6. #define TASK "vmst"
  7.  
  8. using namespace std;
  9.  
  10. const int MAXN = 1e3 + 7,
  11.           MAXM = 15e2 + 7;
  12.  
  13. int N, M;
  14. struct Edge {
  15.     int u, v, c;
  16. } E[MAXM];
  17.  
  18. bool cmp(Edge a, Edge b) {
  19.     return a.c < b.c;
  20. }
  21.  
  22. struct DisjointSets {
  23.     int par[MAXN];
  24.  
  25.     void INIT() {
  26.         for (int i = 0; i < MAXN; ++i) {
  27.             par[i] = -1;
  28.         }
  29.     }
  30.  
  31.     int FIND(int v) {
  32.         return (par[v] < 0) ? (v) : (par[v] = FIND(par[v]));
  33.     }
  34.  
  35.     void MERGE(int u, int v) {
  36.         u = FIND(u);
  37.         v = FIND(v);
  38.  
  39.         if (u == v) {
  40.             return;
  41.         }
  42.  
  43.         if (u > v) {
  44.             swap(u, v);
  45.         }
  46.  
  47.         par[u] += par[v];
  48.         par[v] = u;
  49.     }
  50. } DS;
  51.  
  52. int ANS = 0;
  53.  
  54. void SOLVE(int id) {
  55.     sort(E + 1, E + M + 1, cmp);
  56.     DS.INIT();
  57.  
  58.     for (int i = 1; i <= M; ++i) {
  59.         if (DS.FIND(E[i].u) == DS.FIND(E[i].v)) {
  60.             continue;
  61.         }
  62.  
  63.         cout << E[i].u << ' ' << E[i].v << '\n';
  64.  
  65.         DS.MERGE(E[i].u, E[i].v);
  66.  
  67.         E[i].c += 2 - id;
  68.     }
  69. }
  70.  
  71. main() {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(NULL);
  74.     cout.tie(NULL);
  75.  
  76. #ifndef ONLINE_JUDGE
  77. 	freopen(TASK".inp", "r", stdin);
  78. 	freopen(TASK".out", "w", stdout);
  79. #endif
  80.  
  81.     cin >> N >> M;
  82.     for (int i = 1; i <= M; ++i) {
  83.         cin >> E[i].u >> E[i].v;
  84.     }
  85.  
  86.     cout << 3 << '\n';
  87.     for (int i = 0; i < 3; ++i) {
  88.         SOLVE(i);
  89.     }
  90.  
  91. }
  92.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/onVG86
language:
C++ (gcc 8.3)
created:
30 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!