Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.77 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. ifstream in("conexidad.in");
  8. ofstream out("conexidad.out");
  9.  
  10. void DFS(const vector<vector<int>>& graph,
  11.          vector<bool>& marked,
  12.          int start) {
  13.     marked[start] = true;
  14.  
  15.     for (const int v : graph[start])
  16.         if (!marked[v])
  17.             DFS(graph, marked, v);
  18. }
  19.  
  20. vector<int> extract_vert(const vector<bool>& marked) {
  21.     vector<int> vert;
  22.  
  23.     for (int i = 1; i < marked.size(); i++)
  24.         if (marked[i] == true)
  25.             vert.push_back(i);
  26.  
  27.     return vert;
  28. }
  29.  
  30. vector<vector<int>> get_components(const vector<vector<int>>& graph) {
  31.     vector<bool> marked(graph.size(), false);
  32.  
  33.     vector<vector<int>> components;
  34.  
  35.     for (int i = 1; i < marked.size(); i++)
  36.         if (marked[i] == false) {
  37.             for (int j = 1; j <= i; j++)
  38.                 marked[j] = false;
  39.  
  40.             DFS(graph, marked, i);
  41.  
  42.             components.push_back(extract_vert(marked));
  43.         }
  44.  
  45.     return components;
  46. }
  47.  
  48. int extract_min_edges_vert(const vector<int>& max_extra,
  49.                            const vector<int>& vert) {
  50.     int min = 999999;
  51.     int min_index = 0;
  52.  
  53.     for (int v : vert)
  54.         if (max_extra[v] < min) {
  55.             min = max_extra[v];
  56.  
  57.             min_index = v;
  58.         }
  59.  
  60.     return min_index;
  61. }
  62.  
  63. int main() {
  64.     int vertices, edges;
  65.     in >> vertices >> edges;
  66.  
  67.     vector<vector<int>> graph(vertices + 1);
  68.  
  69.     for (int i = 0; i < edges; i++) {
  70.         int start, end;
  71.         in >> start >> end;
  72.  
  73.         graph[start].push_back(end);
  74.         graph[end].push_back(start);
  75.     }
  76.  
  77.     vector<vector<int>> components = get_components(graph);
  78.  
  79.     sort(components.begin(), components.end()),
  80.         [](const vector<int>& a, const vector<int>& b) { return a.size() > b.size(); };
  81.  
  82.     vector<int> max_extra(vertices + 1, 0);
  83.     vector<pair<int, int>> added_edges;
  84.  
  85.     while (components.size() > 1) {
  86.         int v = extract_min_edges_vert(max_extra, components[0]);
  87.  
  88.         added_edges.push_back(make_pair(v, components[1][0]));
  89.  
  90.         max_extra[v] += 1;
  91.         max_extra[components[1][0]] += 1;
  92.  
  93.         vector<int> new_set;
  94.  
  95.         set_union(components[0].begin(), components[0].end(),
  96.                   components[1].begin(), components[1].end(),
  97.                   back_inserter(new_set));
  98.  
  99.         components[0] = new_set;
  100.         components.erase(components.begin() + 1);
  101.     }
  102.  
  103.     int max_ = 0;
  104.     for (int i = 1; i < max_extra.size(); i++)
  105.         if (max_extra[i] > max_)
  106.             max_ = max_extra[i];
  107.  
  108.     out << max_ << '\n';
  109.     out << added_edges.size() << '\n';
  110.     for (auto const& edge : added_edges)
  111.         out << edge.first << " " << edge.second << '\n';
  112.  
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement