題目大意這樣，給出一些節(jié)點(diǎn)，給出3種命令：
1、將a,b聯(lián)通
2、查詢a,b的聯(lián)通狀況
3、刪除鏈接a的邊。（如果之前a,c通過b聯(lián)通，那么刪除b的聯(lián)通關(guān)系后a,c仍然認(rèn)為聯(lián)通）
1，2兩種操作乍一看MS是并查集，但是第三種狀況讓人很惱火，尤其是想用路徑壓縮技巧的時(shí)候。那么，我們不妨轉(zhuǎn)換下思路，刪除a的聯(lián)通關(guān)系可以認(rèn)為將a節(jié)點(diǎn)重標(biāo)號，把之前那個(gè)a節(jié)點(diǎn)認(rèn)為是虛擬節(jié)點(diǎn)，這樣聯(lián)通性啥的都好保證了。詳細(xì)請看代碼：
Source Code
| Problem: 3908 | | User: yzhw |
| Memory: 1096K | | Time: 47MS |
| Language: G++ | | Result: Accepted |
# include <cstdio>
# define N 100000
using namespace std;
int set[N],id[N];
int find(int pos)
{
if(set[pos]==pos) return pos;
else return set[pos]=find(set[pos]);
}
void uni(int a,int b)
{
set[find(a)]=find(b);
}
int main()
{
int num;
while(scanf("%d",&num)!=EOF)
{
int c=num+1,n1=0,n2=0;
for(int i=1;i<N;i++) set[i]=i;
for(int i=1;i<=num;i++) id[i]=i;
char jud[5];
while(scanf("%s",jud)&&*jud!='e')
{
int a,b;
switch(*jud)
{
case 'c':
scanf("%d%d",&a,&b);
uni(id[a],id[b]);
break;
case 'd':
scanf("%d",&a);
id[a]=c++;
break;
case 'q':
scanf("%d%d",&a,&b);
if(find(id[a])==find(id[b])) n1++;
else n2++;
break;
};
}
printf("%d , %d\n",n1,n2);
}
return 0;
}