알고리즘 - 집합 삭제 점 조작 가상 부모 점
13196 단어 나의 알고리즘
Initially no relationships exist between any pair of the junk emails, so the number of distinct characteristics at that time is N.
Please help us keep track of any necessary information to solve our problem. InputThere are multiple test cases in the input file.
Each test case starts with two integers, N and M (1 ≤ N ≤ 10 5 , 1 ≤ M ≤ 10 6), the number of email samples and the number of operations. M lines follow, each line is one of the two formats described above.
Two successive test cases are separated by a blank line. A case with N = 0 and M = 0 indicates the end of the input file, and should not be processed by your program.OutputFor each test case, please print a single integer, the number of distinct common characteristics, to the console. Follow the format as indicated in the sample below. Sample Input 5 6 M 0 1 M 1 2 M 1 3 S 1 M 1 2 S 3
3 1 M 1 2
0 0 Sample Output Case #1: 3 Case #2: 2
#include
#include
#include
#include
#include
using namespace std;
int rt[2000010],vis[2000010];
int f(int x)
{
if(x==rt[x]) return x;
return rt[x]=f(rt[x]);
}
void merge(int x,int y)
{
int rx=f(x),ry=f(y);
rt[ry]=rx;
}
int main()
{
int n,m,t=0;
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
t++;
char ch;
for(int i=0;i<n;i++){// n
rt[i]=i+n;
}
for(int i=n;i<=n+n+m;i++){// n
rt[i]=i; // m , m
}
int flag=n+n;
int x,y;
for(int i=0;i<m;i++){
cin>>ch;
if(ch=='M') {
scanf("%d%d",&x,&y);
merge(x,y);
}
else if(ch=='S'){
scanf("%d",&x);
rt[x]=flag++;
}
}
memset(vis,0,sizeof(vis));
int cnt=0;
for(int i=0;i<n;i++){
int visit=f(i);
if(!vis[visit]){
cnt++;
vis[visit]=1;
}
}
printf("Case #%d: %d
",t,cnt);
}
return 0;
}