Solution UVA: 10608 - Friends

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10608 - Friends	Accepted	C++11	0.010	0.000	3455	1 mins ago

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

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

Suggest:

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

Template: Disjoint Set Union (vnoi.info)

void make_set(int v) {
    lab[u] = -1;
}

int find_set(int v) {
    return lab[v] < 0 ? v : lab[v] = find_set(lab[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    
    if (a != b) {
        if (lab[a] > lab[b]) swap(a, b);
        lab[a] += lab[b];
        lab[b] = a;
    }
}

Instead of implementing the DSU data structure using two arrays, only one array, lab, is used.

If lab[v] is negative, then v is the root of a tree and -lab[v] is the number of vertices in that tree. If lab[v] is positive, then lab[v] is the parent of vertex v.

=> Result is -min(lab[i])

#include<bits/stdc++.h>

using namespace std;

int lab[1000111];

void make_set(int v) {

    lab[v] = -1;

}

int find_set(int v) {

    return lab[v] < 0 ? v : lab[v] = find_set(lab[v]);

}

void union_sets(int a, int b) {

    a = find_set(a);

    b = find_set(b);

    if (a != b) {

        if (lab[a] > lab[b]) swap(a, b);

        lab[a] += lab[b];

        lab[b] = a;

    }

}

int main(){

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

   

    int t,v,e,a,b;  cin >> t;

    while(t--){

        cin >> v >> e;

       

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

            make_set(i);

           

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

            cin >> a >> b;

            union_sets(a, b);

        }

       

        int res= lab[1];  

        for(int i=2; i<=v; i++)

            res= min(lab[i], res);

        cout<<-res<<"\n";

    }

}