Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* La idea principal es utilizar union-find disjoint set
* Tener cuidado con la lectura. Usar getchar() para leer saltos de linea (\n)
*
* */
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
vi P,R,S;//padres,ranking,set size
int N;//numero de conjuntos
void inicializar(int n){
N=n;
R.assign(N,0);
S.assign(N,1);
P.assign(N,0);
for(int i=0;i<N;i++)
P[i]=i;
}
int findSet(int x){
return x==P[x]?x:P[x]=findSet(P[x]);
}
int isSameSet(int x, int y){
return findSet(x)==findSet(y)?1:0;
}
void unionSet(int x, int y){
if(!isSameSet(x,y)){
int p1=findSet(x);
int p2=findSet(y);
N--;
//para mntener corto el arbol
if(R[p1]>R[p2]){
P[p2]=p1;
S[p1]+=S[p2];
}
else{
P[p1]=p2;
S[p2]+=S[p1];
if(R[p1]==R[p2])
R[p2]++;
}
}
}
int c,i;//correctas/incorrectas
int t,n;
char op,op2;
int main(){
int x,y;
scanf("%d",&t);
while(t--){
scanf("%d\n",&n);
inicializar(n);
while((op=getchar())!=EOF && op!='\n'){
scanf("%d %d",&x,&y);
getchar();
if(op=='c')
unionSet(x-1,y-1);
else
isSameSet(x-1,y-1)==1?c++:i++;
}
printf("%d,%d\n",c,i);
if(t)
printf("\n");
c=i=0;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.