思路：并查集一套带走。
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; }如有不当之处欢迎指出！
