Solution UVA: 793 - Network Connections

 Log:

#		Problem	Verdict	Language	Run Time	Submission Date
29222250	793	Network Connections	Accepted	C++11	0.020	2024-02-21 09:27:35

 
Suggest:
- First, you must search Google to know algorithm Union-Find Disjoint Sets

-Then, you only need care to 2 function below:

<1> this function have effect to find they group of u

int root(int u){
     return fa[u]=( fa[u]==u ? u : root(fa[u]) );
}

<2> this function have effect to join u and v to 1 group

void join(int u, int v){
     fa[root(u)]=root(v);
}

NOTE: although i forget detail but i still ez solve problem because i know effect of function

#include<bits/stdc++.h>

#define N 1000111

#define FOR(i, a, b) for(int i=a; i<=b; i++)

using namespace std;

int n,t;

int fa[N];

void Reset(){

FOR(i, 1, n) fa[i]= i;

}

int root(int u){

return fa[u]=( fa[u]==u ? u : root(fa[u]) );

}

void join(int u, int v){

fa[root(u)]=root(v);

}

void Scanf(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

cin >> t;

while(t--){

cin >> n;

cin.ignore();

Reset();

string s;

int True= 0, False= 0, u, v;

while(getline(cin, s)){

if (s=="") break;

char kind= s[0];

string s1= "";

int i;

for(i=2; s[i] != ' '; i++)

s1 += s[i];

u=stoi(s1);

i++;

s1="";

for(i=i; s[i]; i++)

s1 += s[i];

v=stoi(s1);

if (kind == 'c'){

join(u, v);

}

else{

if (root(u) == root(v)){

True++;

}

else False++;

}

}

cout<<True<<","<<False<<"\n";

if (t>0) cout<<"\n";

}

}

int main(){

Scanf();

}

 

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";

    }

}