How Many Tables

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-06-13 16-05-22
  4**/
  5
  6#include <bits/stdc++.h>
  7
  8using namespace std;
  9
 10#ifdef DEBUG
 11string to_string(string s) {
 12	return '"' + s + '"';
 13}
 14
 15string to_string(const char* s) {
 16	return to_string((string) s);
 17}
 18
 19string to_string(bool b) {
 20return (b ? "true" : "false");
 21}
 22
 23template <typename A, typename B>
 24string to_string(pair<A, B> p) {
 25	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
 26}
 27
 28template <typename A>
 29string to_string(A v) {
 30	bool first = true;
 31	string res = "{";
 32	for (const auto &x : v) {
 33		if (!first) {
 34			res += ", ";
 35		}
 36		first = false;
 37		res += to_string(x);
 38	}
 39	res += "}";
 40	return res;
 41}
 42
 43void debug_out() { cerr << endl; }
 44
 45template <typename Head, typename... Tail>
 46void debug_out(Head H, Tail... T) {
 47	cerr << " " << to_string(H);
 48	debug_out(T...);
 49}
 50#endif
 51
 52#ifdef DEBUG
 53#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
 54#else
 55#define debug(...) 17
 56#endif
 57
 58#ifdef DEBUG
 59#define FAST_IO 17
 60#define cout cout << "-->"
 61#else
 62#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 63#define endl '\n'
 64#endif
 65
 66#define LL long long
 67#define ULL unsigned long long
 68#define rep(i, n) for(int i = 0; i < (n); ++i)
 69#define reep(i, n) for(int i = 0; i <= (n); ++i)
 70#define lop(i, a, n) for(int i = a; i < (n); ++i)
 71#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 72#define ALL(v) (v).begin(), (v).end()
 73#define PB push_back
 74#define VI vector<int>
 75#define PII pair<int,int>
 76#define FI first
 77#define SE second
 78#define SZ(x) ((int)(x).size())
 79
 80const double EPS = 1e-6;
 81const double PI = acos(-1.0);
 82const int INF = 0x3f3f3f3f;
 83const LL LINF = 0x7f7f7f7f7f7f7f7f;
 84const int MAXN = (int)1e6 + 10;
 85const int MOD = (int)1e9 + 7;
 86
 87class UnionFind{
 88	private:
 89		int * parent;
 90		int * rank;
 91		int count;
 92	public:
 93		UnionFind(int n){
 94			parent = new int[n];
 95			rank = new int[n];
 96			this->count = n;
 97			for(int i = 0; i < n; ++i){
 98				parent[i] = i;
 99				rank[i] = 1;
100			}
101		}
102		~UnionFind(){
103			delete[] parent;
104			delete[] rank;
105		}
106
107		int find(int p){
108			while(p != parent[p]){
109				p = parent[p];
110			}
111			return p;
112		}
113
114		bool isConnected(int p, int q){
115			return find(p) == find(q);
116		}
117
118		void unionElements(int p, int q){
119			int pRoot = find(p);
120			int qRoot = find(q);
121
122			if(pRoot == qRoot) return;
123
124			if(rank[pRoot] < rank[qRoot]){
125				parent[pRoot] = qRoot;
126			}else if(rank[qRoot] < rank[pRoot]){
127				parent[qRoot] = pRoot;
128			}else{
129				parent[pRoot] = qRoot;
130				rank[qRoot] += 1;
131			}
132		}
133
134		int cnt(){
135			int cnt = 0;
136			for(int i = 0; i < this->count; ++i){
137				if(parent[i] == i) ++cnt;
138			}
139			return cnt;
140		}
141};
142
143int main(){
144	FAST_IO;
145
146	int t;
147	cin >> t;
148	while(t--){
149		int n, m, p, q;
150		cin >> n >> m;
151		UnionFind uf = UnionFind(n);
152		while(m--){
153			cin >> p >> q;
154			uf.unionElements(p-1, q-1);
155		}
156		cout << uf.cnt() << endl;
157	}
158
159	return 0;
160}