fork(7) download
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6.  
  7. /*
  8. Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева
  9. */
  10. struct edge{
  11. int x, y; //вершины
  12. edge(){}
  13. edge(int a, int b){
  14. x = a;
  15. y = b;
  16. }
  17. };
  18.  
  19. int main() {
  20. int n, m;
  21. cin >> n >> m;
  22.  
  23. vector <edge> graph (m); //ребра исходного графа
  24. vector <edge> tree; //ребра дерева
  25. vector <int> variety (n); //множество вершин
  26.  
  27. /*
  28. variety[n] = m - вершина n принадлежит множеству m.
  29. Следующий цикл определяет для каждой вершины свое множество
  30. */
  31. for (int i = 0; i < n; i++){
  32. variety[i] = i;
  33. }
  34.  
  35. /*
  36. Заполняем ребра исходного графа значениями из стандартного ввода
  37. */
  38. for (int i = 0; i < m; i++){
  39. int a, b;
  40. cin >> a >> b;
  41. graph[i].x = a;
  42. graph[i].y = b;
  43. }
  44.  
  45. /*
  46. Проверяем вершины каждого ребра.
  47. Если вершины не принадлежат одному и тому же множеству,
  48. но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество
  49. */
  50. for (int i = 0; i < m; i++){
  51. int a = graph[i].x;
  52. int b = graph[i].y;
  53. if (variety[a] != variety[b]){
  54. tree.push_back(graph[i]);
  55. int old_variety = variety[b], new_variety = variety[a];
  56. for (int j = 0; j < n; j++){
  57. if (variety[j] == old_variety){
  58. variety[j] = new_variety;
  59. }
  60. }
  61.  
  62.  
  63.  
  64. }
  65. }
  66.  
  67.  
  68. for(int i = 0; i < n-1; i++){ //по принципу построения дерева, оно содержит n-1 ребро
  69. cout << tree[i].x << " " << tree[i].y;
  70. if (i != n-2){
  71. cout << endl;
  72. }
  73. }
  74. return 0;
  75. }
Success #stdin #stdout 0s 3420KB
stdin
4 5
4 3
2 4
2 3
1 2
1 3
stdout
4 3
2 4
1 2