海盜同伙問(wèn)題：
現(xiàn)在有10個(gè)海盜。
1號(hào)海盜和2號(hào)海盜是同伙
3號(hào)海盜和4號(hào)海盜是同伙
5號(hào)海盜和2號(hào)海盜是同伙
4號(hào)海盜和6號(hào)海盜是同伙
2號(hào)海盜和6號(hào)海盜是同伙
8號(hào)海盜和7號(hào)海盜是同伙
9號(hào)海盜和7號(hào)海盜是同伙
1號(hào)海盜和6號(hào)海盜是同伙
2號(hào)海盜和4號(hào)海盜是同伙
強(qiáng)盜同伙的同伙也是同伙，共有多少個(gè)獨(dú)立的犯罪團(tuán)伙者祖？
// 遞歸函數(shù) 直到找到犯罪團(tuán)伙的最高領(lǐng)導(dǎo)人的編號(hào)
int getf(int v,int f[]) {
if (f[v] == v) {
return v;
}else {
// 路徑壓縮 每次在函數(shù)返回時(shí)轮蜕，順帶把路上遇見(jiàn)的人的Boss改為最后找到的最高領(lǐng)導(dǎo)人的編號(hào)
f[v] = getf(f[v], f);
return f[v];
}
}
void merge(int v,int u,int f[]) {
int t1 = getf(v, f);
int t2 = getf(u, f);
if (t1 != t2) {
// 靠左原則
f[t2] = t1;
}
return ;
}
-(void)test1 {
int f[11];
// 數(shù)組里存的是元素在數(shù)組中的下標(biāo)
for (int i=1; i<=10; i++) {
f[i] = i;
}
//1號(hào)海盜和2號(hào)海盜是同伙
merge(1, 2, f);
//3號(hào)海盜和4號(hào)海盜是同伙
merge(3, 4, f);
//5號(hào)海盜和2號(hào)海盜是同伙
merge(5, 2, f);
//4號(hào)海盜和6號(hào)海盜是同伙
merge(4, 6, f);
//2號(hào)海盜和6號(hào)海盜是同伙
merge(2, 6, f);
//8號(hào)海盜和7號(hào)海盜是同伙
merge(8, 7, f);
//9號(hào)海盜和7號(hào)海盜是同伙
merge(9, 7, f);
//1號(hào)海盜和6號(hào)海盜是同伙
merge(1, 6, f);
//2號(hào)海盜和4號(hào)海盜是同伙
merge(2, 4, f);
int sum=0;
for (int i=1; i<=10; i++) {
if (f[i] == i) {
sum ++;
}
NSLog(@"%d",f[i]);
}
printf("\n");
printf("共有%d個(gè)犯罪團(tuán)伙",sum);
}
