https://www.acwing.com/problem/content/description/838/
看到這個題，以前好像涉及過，對每個點設定一個共同的祖先，然后表示是這個祖先的手下，表示一個集合，
然后我寫來寫去，老是超時，這讓我很疑惑，寫了三個 版本，最后一個版本就AC了，大家有興趣可以看看解釋一下為什么呢，
第一種版本
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,p[N];
void m_c(int x,int y)
{
while(x!=p[x]) x=p[x];
while(y!=p[y]) y=p[y];
if(x==y)
return;
p[y]=p[x]=x;
}
bool q(int x,int y)
{
while(x!=p[x]) x=p[x];
while(y!=p[y]) y=p[y];
if(x==y) return true;
return false;
}
int main(void)
{
int a,b;
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++)
{
string s;
cin>>s>>a>>b;
if(s=="M")
m_c(a,b);
else
{
if(q(a,b))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
}
這是只能過前六個樣例，第七個樣例超時，思路看起來應該沒有問題，
第二個版本，看大家的題解寫了一種版本
#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N],m,n;
int find(int x)
{
if(p[x]!=x)
return find(p[x]);
return p[x];
}
int main(void)
{
cin>>n>>m;
int a,b;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++)
{
char s[10];
scanf("%s%d%d",s,&a,&b);
if(*s=='M')
p[find(a)]=find(b);
else
cout<<(find(a)==find(b)?"Yes":"No")<<endl;
}
}
這還是沒有過，
當我改了一個地方，我就AC了，但是我還是沒有明白三個邏輯結果為什么不同，
#include<iostream>
using namespace std;
const int N=1e5+10;
int p[N];
int find(int x)
{
if(p[x]!=x)
p[x] = find(p[x]);
return p[x];
}
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++)
{
char s[2];
scanf("%s%d%d",s,&a,&b);
if(*s=='M')
p[find(a)]=find(b);
else
cout<<(find(a)==find(b)?"Yes":"No")<<endl;
}
}
前兩個是WA了，但是第三個我就改了一下find（）函式我就過了，這是為什么呢？？
作者：Bitterwine–就是我啦
鏈接：https://www.acwing.com/problem/content/discussion/content/1864/
來源：AcWing
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260707.html
標籤：其他
上一篇：Protecting Poorly Chosen Secrets from Guessing Attacks論文筆記