并查集板子题
Code
/**
* author: Akvicor
* created: 2019-06-13 15-21-28
**/
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <complex>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
using namespace std;
#ifdef DEBUG
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#endif
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 17
#endif
#ifdef DEBUG
#define FAST_IO 17
#define cout cout << "-->"
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif
#define LL long long
#define ULL unsigned long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define PB push_back
#define VI vector<int>
#define PII pair<int,int>
#define FI first
#define SE second
#define SZ(x) ((int)(x).size())
const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;
const int MAXN = (int)1e6 + 10;
const int MOD = (int)1e9 + 7;
class UnionFind{
private:
int * parent;
int * sz;
int count;
public:
UnionFind(int n){
parent = new int[n];
sz = new int[n];
this->count = n;
for(int i = 0; i < n; ++i){
parent[i] = i;
sz[i] = 1;
}
}
~UnionFind(){
delete[] parent;
delete[] sz;
}
int find(int p){
while(p != parent[p])
p = parent[p];
return p;
}
bool isConnected(int p, int q){
return find(p) == find(q);
}
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
if(sz[pRoot] < sz[qRoot]){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
int cnt(int p){
return sz[find(p)];
}
};
int n, m;
int main(){
FAST_IO;
while(cin >> n >> m){
if(n == 0 && m == 0) break;
int k, p, q;
UnionFind uf = UnionFind(n);
while(m--){
cin >> k;
if(k == 0) continue;
if(k == 1){cin >> k; continue;}
cin >> p;
while(--k){
cin >> q;
uf.unionElements(p, q);
}
}
cout << uf.cnt(0) << endl;
}
return 0;
}