Topic connection

Each player has some fans. The condition for a fan to watch a player's game is

• He likes the player

• People who like the same player like this player.

The relationship between players and fans can be changed dynamically. Ask how many players are invited to play after each change so that all fans can watch the game.

The change is that for the two numbers of b a nd a, b is the fan number and a is the player number. If b is a fan of a, now b is not a fan of a, on the contrary, b becomes a fan of A.

It is equivalent to segment tree divide and conquer. For each query, throw it into each leaf node of the segment tree, and then record the interval of each relationship. Use segment tree interval coverage.

cnt represents the number of Unicom blocks, cnta represents the number of individual players, and cntb represents the number of individual fans,

If cntb is not 0, output - 1, otherwise output cnt - cnta

The connection block is represented by the joint query set. Each time the line segment tree is pushed down, the current joint query set status should be recorded, and the data should be restored when returning.

At this time, the merge set cannot be compressed by path, and heuristic merging is required when merging the merge set, that is, small sets are connected to large sets.

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+100;
typedef pair<int,int>P;
struct recv{
	int a,asz,b,bsz;
	int cnt,cnta,cntb;
};
struct node{
	int l,r; // left and right 
	vector<P>e;
	vector<recv> rec;
}tr[N<<2];
int n,m,q,f[N<<1],cnt,cnta,cntb,ans[N<<1],sz[N<<1];

map<int,int>mp[N];
int find(int k){
	if (f[k] == k) return k;
	return find(f[k]);
}

void build(int now, int l, int r){
	tr[now].l = l; tr[now].r = r;
	tr[now].e.clear();
	tr[now].rec.clear();
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(now << 1, l, mid);
	build(now << 1 | 1, mid+1, r);
}
void update(int now, int l, int r, P p){
	if(l <= tr[now].l &&  r >= tr[now].r) {
		tr[now].e.push_back(p);
		return;
	}
	int mid = (tr[now].l + tr[now].r) >> 1;
	if (l <= mid) update(now << 1, l, r, p);
	if (r >= mid + 1) update(now << 1 | 1,l, r, p);
}

void solve(int now){
	int a,b,len = 0;
	recv tmp;
	for (auto it: tr[now].e){
		a = find(it.first); b = find(it.second);
		if (a == b) continue;
		tmp.cnt = cnt; tmp.cnta = cnta; tmp.cntb = cntb;
		cnt--;
		if (sz[a] == 1) cnta--;
		if (sz[b] == 1) cntb--;
		if (sz[a] < sz[b]) swap(a,b);
		tmp.a = a; tmp.b = b;
		tmp.asz = sz[a];
		tmp.bsz = sz[b];
		f[b] = a;
		sz[a] += sz[b];
		tr[now].rec.push_back(tmp);
		len++;
	}
	if (tr[now].l == tr[now].r){
		if (cntb != 0){
			ans[tr[now].l] = -1;
		} else {
			ans[tr[now].l] = cnt - cnta;
		}
	} else {
		solve(now << 1);
		solve(now << 1 | 1);
	}
	for (int i = len-1; i >= 0; --i){
		tmp = tr[now].rec[i];
		cnt = tmp.cnt;
		cnta = tmp.cnta;
		cntb = tmp.cntb;
		f[tmp.a] = tmp.a;
		f[tmp.b] = tmp.b;
		sz[tmp.a] = tmp.asz;
		sz[tmp.b] = tmp.bsz;
	}
}

void prework(){
	int a,b,k;
	// a is player  b is fan
	scanf("%d%d%d",&n,&m,&q);
	build(1,1,q+1);
	for (int i = 1; i <= n; ++i){
		scanf("%d",&k);
		for (int j = 1; j <= k; ++j){
			scanf("%d",&b);	
			mp[i][b] = 1;
		}
	}
	for (int i = 2; i <= q + 1; ++i){
		scanf("%d%d",&b,&a);
		if (mp[a][b] == 0){
			mp[a][b] = i;
		} else {
			update(1, mp[a][b], i-1,P{a,b+n});
			mp[a][b] = 0;
		}
	}
	for (int i = 1; i <= n; ++i){
		for (auto it: mp[i]){
			if (it.second){
				update(1, it.second, q+1, P{i, it.first+n});
			}
		}
	}
	cnt = n+m;
	cnta = n; cntb = m;
	for (int i = 0; i <= cnt; ++i){
		f[i] = i;
		sz[i] = 1;
	}
}
int main(){
	prework();	
	solve(1);
	for (int i = 2; i <= q+1; ++i)
		printf("%d\n",ans[i]);
	return 0;
}