#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int parent[26]; int countNodes[26]; int getparent(int n) { if(parent[n]==n) return n; else return parent[n]=getparent(parent[n]); } void unite(int a,int b) { parent[getparent(a)]=getparent(b); } int main() { int t; string str; scanf("%d",&t); getchar(); while(t–) { str=""; for(int i=0;i<26;i++) { parent[i]=i; countNodes[i]=0; } while(getline(cin,str),str[0]!='*') { unite(str[1]-'A',str[3]-'A'); }
Category: Union Find
793
#include <iostream> #include <string.h> #include <vector> #include <cstdio> #define SZ 1000001 using namespace std; int par[SZ]; void init() { for(int i=0;i<SZ;i++) par[i]=i; } int find(int a) { if(par[a]==a) return a; else return find(par[a]); } int main() { int t; int n,a,b; int Ycnt,Ncnt; char cmnd,ch; bool f=false; cin>>t; getchar(); while(t–) { cin>>n; init(); getchar(); Ycnt=0;