思路:并查集一套带走。
AC代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 10000+5;
int par[maxn], vis[maxn];
int findRoot(int x) {
return x == par[x] ? x : par[x] = findRoot(par[x]);
}
void unionSet(int x, int y) {
x = findRoot(x);
y = findRoot(y);
if(x != y) {
par[x] = y;
}
}
void init(int n) {
memset(vis, 0, sizeof(vis));
for(int i = 0; i <= n; i++) {
par[i] = i;
}
}
int main() {
int n, k, q, len;
len = -1;
scanf("%d", &n);
init(maxn);
for(int i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &k, &x);
len = max(len, x);
for(int j = 1; j < k; j++) {
scanf("%d", &y);
len = max(len, y);
unionSet(x, y);
x = y;
}
}
int tol = 0;
for(int i = 1; i <= len; i++) {
int root = findRoot(i);
if(!vis[root]) {
vis[root] = 1;
tol++;
}
}
printf("%d %d\n", tol, len);
scanf("%d", &q);
int x, y;
for(int i = 0; i < q; i++) {
scanf("%d%d", &x, &y);
x = findRoot(x);
y = findRoot(y);
if(x == y) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
如有不当之处欢迎指出!