4 solutions
-
4
#include<iostream> using namespace std; const int N=5e3+7; int f[N]; //初始化每个人的祖先都是自己 void init(){ for(int i=1;i<N;i++) f[i]=i; } //查找x的祖先 int fin(int x){ while(x!=f[x]) x=f[x]; return x; } //合并两个人的祖先 void merge(int a,int b){ a=fin(a); b=fin(b); f[b]=a; } int main(){ init(); int n,p,m; cin>>n>>m>>p; //构建亲戚关系 for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; merge(a,b); } //开始询问 while(p--){ int a,b; cin>>a>>b; if(fin(a)==fin(b)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
-
2
#include<iostream> #include<vector> #include<stack> using namespace std; static const int MAX = 10007; static const int NIL = -1; //使用vector实现邻接表 int n; vector<int>G[MAX]; int color[MAX]; //深搜实现连通图的染色 void dfs(int r,int c){ stack<int>S; S.push(r); color[r]=c; while(!S.empty()){ int u=S.top();S.pop(); for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(color[v]==NIL){ color[v]=c; S.push(v); } } } } //遍历图,逐个染色 void assignColor(){ int id=1; for(int i=0;i<=n;i++)color[i]=NIL; for(int i=0;i<=n;i++){ if(color[i]==NIL)dfs(i,id++); } } int main(){ int s,t,m,q; cin>>n>>m>>q; for(int i=0;i<m;i++){ cin>>s>>t; G[s].push_back(t); G[t].push_back(s); } assignColor(); for(int i=0;i<q;i++){ cin>>s>>t; if(color[s]==color[t])cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
-
1
#include <bits/stdc++.h> using namespace std; int w[5007]; int find(int x){//找祖先 if(w[x]==x) return x; return w[x]=find(w[x]);//关键点:让每个人都直接指向自己的祖先,便于快速查找 } int main(){ int n,m,p,x,y; cin>>n>>m>>p; for(int i=1;i<n;i++) w[i]=i;//自己为自己祖先 for(int i=0;i<m;i++){ cin>>x>>y; w[find(x)]=find(y);//添加关系 } for(int i=0;i<p;i++){//判断 cin>>x>>y; if(find(x)==find(y)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
-
0
n, m, p = map(int, input().split()) f = [i for i in range(n+1)] def find(x): if(f[x]!=x): f[x] = find(f[x]) return f[x] def union(a, b): a = find(a) b = find(b) if(a != b): f[a] = b for _ in range(m): a, b = map(int, input().split()) union(a, b) for _ in range(p): i, j = map(int, input().split()) print("Yes" if find(i)==find(j) else "No")
- 1
Information
- ID
- 1257
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 4
- Tags
- # Submissions
- 141
- Accepted
- 66
- Uploaded By