Untitled
c_cpp
2 months ago
1.6 kB
6
Indexable
Never
#include <iostream> #include <vector> #include <cmath> using namespace std; struct Edge { int from, to; }; int findRoot(int node, vector<int>& parent) { if (parent[node] == node) return node; return parent[node] = findRoot(parent[node], parent); } int connectedSum(int graph_nodes, vector<int> graph_from, vector<int> graph_to) { vector<Edge> edges; for (int i = 0; i < graph_from.size(); ++i) { edges.push_back({graph_from[i], graph_to[i]}); } vector<int> parent(graph_nodes + 1); for (int i = 1; i <= graph_nodes; ++i) { parent[i] = i; } for (const Edge& edge : edges) { int rootFrom = findRoot(edge.from, parent); int rootTo = findRoot(edge.to, parent); if (rootFrom != rootTo) { parent[rootTo] = rootFrom; } } vector<int> weights(graph_nodes + 1, 0); for (int i = 1; i <= graph_nodes; ++i) { int root = findRoot(i, parent); weights[root]++; } int sum = 0; for (int w : weights) { if (w > 0) { sum += ceil(sqrt(w)); } } return sum; } int main() { int graph_nodes, graph_edges; cin >> graph_nodes >> graph_edges; vector<int> graph_from(graph_edges), graph_to(graph_edges); for (int i = 0; i < graph_edges; ++i) { cin >> graph_from[i]; } for (int i = 0; i < graph_edges; ++i) { cin >> graph_to[i]; } int result = connectedSum(graph_nodes, graph_from, graph_to); cout << result << endl; return 0; }