4 条题解
-
2
#include <bits/stdc++.h> using namespace std; int n, m, a[10005]; //找v的父节点, 并将其路径上的点全部路径压缩 int getf(int v) { if (a[v] == v) { return v; } a[v] = getf(a[v]); return a[v]; } //合并v和u所在的集合 void merge(int v, int u) { v = getf(v); u = getf(u); if (v != u) { a[u] = v; } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { a[i] = i; } for (int i = 1; i <= m; i++) { int z, x, y; cin >> z >> x >> y; if (z == 1) { merge(x, y); } else { if (getf(x) == getf(y)) { cout << "Y"; } else { cout << "N"; } cout << endl; } } return 0; }
-
1
简单并查集,直接做就行。但是要有一步a[x]=t1,a[y]=t2;来优化并查集,使在递归查找时更快,不然会TLE。
#include<bits/stdc++.h> using namespace std; int n,m,a[400005],k,x,y,z,t1,t2,s; int dg(int x) { if(a[x]==x) return x; else return dg(a[x]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) a[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&z,&x,&y); x++,y++; t1=dg(x),t2=dg(y); a[x]=t1,a[y]=t2; if(z==1&&t1!=t2) a[t1]=y; else if(z==2) printf("%c\n",t1==t2?'Y':'N'); } return 0; }
-
1
基础的并查集操作
#include<bits/stdc++.h> #define mod 998244353 #define ll long long using namespace std; const int N=10005; int n,m,k,s,t,fa[N],ty; int getfa(int x){ return fa[x]==x?x:fa[x]=getfa(fa[x]); } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; iota(fa+1,fa+1+n,1); for (int i=1;i<=m;++i){ cin>>ty>>s>>t; if (ty==1){ s=getfa(s); t=getfa(t); if (s!=t) fa[s]=t; } else { s=getfa(s); t=getfa(t); cout<<(s==t?"Y":"N")<<"\n"; } } }
-
0
这是一个并查集(Disjoint Set)的问题,涉及到两个操作:合并(Union)和查询(Find)。并查集是一种用于管理元素分组的数据结构。
在这个问题中,我们需要处理N个元素和M个操作。首先初始化一个大小为N的并查集,将每个元素初始化为自己的父节点。然后按照给定的操作进行处理:
-
合并操作(op=1):将X和Y所在的集合合并。找到X的根节点和Y的根节点,然后将其中一个根节点的父节点指向另一个根节点,表示这两个元素属于同一个集合。
-
查询操作(op=2):判断X和Y是否属于同一个集合。找到X的根节点和Y的根节点,如果它们的根节点相同,则说明X和Y在同一个集合中,输出"Y";否则,输出"N"
思路:
- 首先读取输入的N和M,创建一个并查集对象。
- 循环M次,处理每个操作:
- 读取操作类型op、元素X和元素Y。
- 如果op=1,执行合并操作,即调用并查集对象的union方法,将X和Y合并。
- 如果op=2,执行查询操作,即调用并查集对象的find方法,判断X和Y是否在同一个集合中,输出结果。
- 完成所有操作后,输出结果。
#include <iostream> #include <vector> class UnionFind { private: std::vector<int> parent; public: UnionFind(int n) : parent(n) { for (int i = 0; i < n; ++i) { parent[i] = i; } } int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void unionSet(int x, int y) { int xRoot = find(x); int yRoot = find(y); if (xRoot != yRoot) { parent[xRoot] = yRoot; } } }; int main() { int n, m; std::cin >> n >> m; UnionFind uf(n); while (m--) { int op, x, y; std::cin >> op >> x >> y; if (op == 1) { uf.unionSet(x - 1, y - 1); } else if (op == 2) { if (uf.find(x - 1) == uf.find(y - 1)) { std::cout << "Y" << std::endl; } else { std::cout << "N" << std::endl; } } } return 0; }
-
- 1
信息
- ID
- 232
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 71
- 已通过
- 41
- 上传者