首页 > 代码库 > 并查集
并查集
n个人 m个关系 p次查询
simple input
9 7 6
2 4
5 7
1 3
8 9
1 2
5 6
2 3
1 2
1 3
1 4
1 5
5 6
8 9
simput output
YES
YES
YES
NO
YES
YES
#include <iostream> using namespace std; const int M = 1e3 + 10; int folk[M]; int dsu(int u) { return u == folk[u] ? u : folk[u] = dsu(folk[u]); } int main() { int n,m; int p; int a, b; scanf("%d", &n); for (int i = 0; i < n; i++) folk[i] = i; scanf("%d", &m); scanf("%d", &p); while (m--) { int u, v; scanf("%d%d", &u, &v); int _u = dsu(u), _v = dsu(v); if (_u != _v) { folk[v] = _u; } } while (p--){ scanf("%d%d", &a, &b); a = dsu(a); b = dsu(b); printf(a == b ? "YES\n" : "NO\n"); } return 0; }
并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。