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();

}