Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- ifstream in("conexidad.in");
- ofstream out("conexidad.out");
- void DFS(const vector<vector<int>>& graph,
- vector<bool>& marked,
- int start) {
- marked[start] = true;
- for (const int v : graph[start])
- if (!marked[v])
- DFS(graph, marked, v);
- }
- vector<int> extract_vert(const vector<bool>& marked) {
- vector<int> vert;
- for (int i = 1; i < marked.size(); i++)
- if (marked[i] == true)
- vert.push_back(i);
- return vert;
- }
- vector<vector<int>> get_components(const vector<vector<int>>& graph) {
- vector<bool> marked(graph.size(), false);
- vector<vector<int>> components;
- for (int i = 1; i < marked.size(); i++)
- if (marked[i] == false) {
- for (int j = 1; j <= i; j++)
- marked[j] = false;
- DFS(graph, marked, i);
- components.push_back(extract_vert(marked));
- }
- return components;
- }
- int extract_min_edges_vert(const vector<int>& max_extra,
- const vector<int>& vert) {
- int min = 999999;
- int min_index = 0;
- for (int v : vert)
- if (max_extra[v] < min) {
- min = max_extra[v];
- min_index = v;
- }
- return min_index;
- }
- int main() {
- int vertices, edges;
- in >> vertices >> edges;
- vector<vector<int>> graph(vertices + 1);
- for (int i = 0; i < edges; i++) {
- int start, end;
- in >> start >> end;
- graph[start].push_back(end);
- graph[end].push_back(start);
- }
- vector<vector<int>> components = get_components(graph);
- sort(components.begin(), components.end()),
- [](const vector<int>& a, const vector<int>& b) { return a.size() > b.size(); };
- vector<int> max_extra(vertices + 1, 0);
- vector<pair<int, int>> added_edges;
- while (components.size() > 1) {
- int v = extract_min_edges_vert(max_extra, components[0]);
- added_edges.push_back(make_pair(v, components[1][0]));
- max_extra[v] += 1;
- max_extra[components[1][0]] += 1;
- vector<int> new_set;
- set_union(components[0].begin(), components[0].end(),
- components[1].begin(), components[1].end(),
- back_inserter(new_set));
- components[0] = new_set;
- components.erase(components.begin() + 1);
- }
- int max_ = 0;
- for (int i = 1; i < max_extra.size(); i++)
- if (max_extra[i] > max_)
- max_ = max_extra[i];
- out << max_ << '\n';
- out << added_edges.size() << '\n';
- for (auto const& edge : added_edges)
- out << edge.first << " " << edge.second << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement