Input
Output
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>
//#include <xfunctional>
#define ll long long
#define PII pair<int, int>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mk make_pair
using namespace std;
int dir1[6][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 },{ 1,1 },{ -1,1 } };
int dir2[6][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 },{ 1,-1 },{ -1,-1 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979;
const int mod = 1e9 + 7;
const int N = 30005;
//if(x<0 || x>=r || y<0 || y>=c)
inline ll read()
{
ll x = 0; bool f = true; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) f = false; c = getchar(); }
while (c >= ‘0‘ && c <= ‘9‘) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? x : -x;
}
int n, m;
int pa[N],num[N],rankn[N];
void makeset(int x)
{
pa[x] = x;
num[x] = 1;
rankn[x] = 0;
}
int findset(int x)
{
int r = x, tmp;
while (pa[r] != r)
r = pa[r];
while (x != r)
{
tmp = pa[x];
pa[x] = r;
x = tmp;
}
return x;
}
void unionset(int x,int y)
{
x = findset(x);
y = findset(y);
if (x == y)
return;
if (rankn[x] > rankn[y])
{
pa[y] = x;
num[x] += num[y];
}
else
{
pa[x] = y;
if (rankn[x] == rankn[y])
rankn[y]++;
num[y] += num[x];
}
}
int main()
{
while (cin >> n >> m)
{
if (m == n && n == 0)
break;
if (m == 0)
{
cout << 1 << endl;
continue;
}
for (int i = 0; i < n; i++)
{
makeset(i);
}
for (int i = 0; i < m; i++)
{
int t, x, y;
cin >> t >> x;
for (int j = 1; j < t; j++)
{
cin >> y;
unionset(x, y);
x = y;
}
}
int root = findset(0);
cout << num[root] << endl;
}
return 0;
}
原文：https://www.cnblogs.com/dealer/p/12741589.html