POJ 3908 Quick answer並列調査セット
本題は並列調査セットの運用であり,削除操作時にその削除された点以外の接続関係が変わらなければ,具体的な操作はこの点を新しい点に変え,1つのid配列でidを更新すればよい.
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int pre[50005], id[50005];
int find(int x)
{
if(pre[x] == x)
return x;
int t = find(pre[x]);
pre[x] = t;
return t;
}
void join(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx != fy)
{
if(fx > fy)
pre[fx] = fy;
else pre[fy] = fx;
}
}
int main()
{
#ifdef LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
int n, i, n1, n2, x, y;
char s[3];
while(scanf("%d", &n) != EOF)
{
n1 = 0, n2 = 0;
for(i = 1; i <= n; i++)
{
pre[i] = i;
id[i] = i;
}
while(scanf("%s", s) != EOF)
{
if(s[0] == 'e')
break;
if(s[0] == 'c')
{
scanf("%d%d", &x, &y);
join(id[x], id[y]);
}
else if(s[0] == 'd')
{
scanf("%d", &x);
id[x] = ++n;
pre[n] = n;
}
else if(s[0] == 'q')
{
scanf("%d%d", &x, &y);
if(find(id[x]) == find(id[y]))
n1++;
else n2++;
}
}
printf("%d , %d
", n1, n2);
}
return 0;
}