Solution UVA: 10685 - Nature

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10685 - Nature	Accepted	C++11	0.100	0.010	721	1 mins ago

Problem: http://uva.onlinejudge.org/external/106/10685.pdf

-This is the problem of finding the largest connected component of a graph and printing the number of vertices in that connected component. (same problem 10608)

Suggest:

-Use the Disjoint-Set Union (DSU) data structure to solve this problem.
Template: Disjoint Set Union (vnoi.info)

void make_set(int v) {
    parent[v] = v;
    sz[v] = 1; // Ban đầu tập hợp chứa v có kích cỡ là 1
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a, b); // Đặt biến a là gốc của cây có kích cỡ lớn hơn
        parent[b] = a;
        sz[a] += sz[b]; // Cập nhật kích cỡ của cây mới gộp lại
    } 
}

int find_set(int v) {
    return v == parent[v] ? v : parent[v] = find_set(parent[v]);
}

- In problem i only swap sz and par to:

    unordered_map<string, int> sz;

    unordered_map<string, string> par;

- Finally, print result is max(sz[v]) with v is vertexs of graph

#include<bits/stdc++.h>

using namespace std;

unordered_map<string, int> sz;

unordered_map<string, string> par;

void make_set(string v) {

    sz[v] = 1;

    par[v] = v;

}

string find_set(string v) {

    return par[v] == v ? v : par[v] = find_set(par[v]);

}

void union_sets(string a, string b) {

    a = find_set(a);

    b = find_set(b);

    if (a != b) {

        if (sz[a] < sz[b]) swap(a, b);

        sz[a] += sz[b];

        par[b] = a;

    }

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    int v,e;

    while(cin >> v >> e){

        if (v==0 && e==0) break;

        sz.clear();

        par.clear();

        vector<string> vec;

       

        for(int i=1; i<=v; i++){

            string x; cin >> x; vec.push_back(x);

            make_set(x);

        }

           

        for(int i=1; i<=e; i++){

            string a,b; cin >> a >> b;

            union_sets(a, b);

        }

       

        int res= -1000111000;  

        for(int i=0; i<vec.size(); i++)

            res= max(sz[vec[i]], res);

        cout<<res<<"\n";

    }

}