题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
const int N =1e4+10;
int n,Q;
int p[N],v[N];
int find(int x)
{
if(p[x]!=x) return p[x]=find(p[x]);
return p[x];
}
void unio(int a,int b)
{
a=find(a),b=find(b);
if(a!=b) p[a]=b;
}
int main()
{
freopen("1.txt","r",stdin);
int n;cin>>n;
for(int i=0;i<N;i++) p[i]=i;
set<int> st;
while(n--)
{
int k;cin>>k;
for(int i=0;i<k;i++)
{
cin>>v[i];
st.insert(v[i]);
if(i) unio(v[i],v[0]);
}
}
int birds=st.size(),tree=0;
for(int i=1;i<=birds;i++) if(p[i]==i) tree++;
cout<<tree<<" "<<birds<<endl;
cin>>Q;
while(Q--)
{
int a,b;cin>>a>>b;
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla