Untitled

mail@pastecode.io avatarunknown
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;
}