传送门:点击打开链接
题意:给出n(<=500)个点和m(<=1e4)条边,形成一个图,查询k(<=1e4)次,对于每个查询,有l和r,输出删除编号[l,r]区间内的边后形成的连通块的个数。
思路:连通块肯定想到用并查集去维护。然后看到n比较小,所以可能可以每次查询里面复杂度带有n。
因为删边用并查集不是很好维护,所以我们可能要想到能不能避免边的删除,那么很容易的想到前缀和思想。
用PL[l]来保存[1,l]前l条边组成的图里面的并查集父节点的情况;
用PR[r]来保存[r,n]后r条边组成的图里面的并查集父节点的情况;
那么对于每一次查询[l,r]我只要把PL[l-1]和PR[r+1]的并查集父节点情况再次合并,也就是把两个并查集数组合并,那么就能得到新的并查集,这就是此刻图的情况了。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1const int MX = 1e4 + 5;
const int MP = 5e2 + 5;int n, m;
int PL[MX][MP], PR[MX][MP], tp[MP];
int L[MX], R[MX];int find(int P[], int x) {return P[x] == x ? x : (P[x] = find(P, P[x]));
}void presolve() {for(int i = 1; i <= n; i++) PL[0][i] = i;for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) PL[i][j] = PL[i - 1][j];int p1 = find(PL[i], L[i]), p2 = find(PL[i], R[i]);if(p1 != p2) PL[i][p2] = p1;}for(int i = 1; i <= n; i++) PR[m + 1][i] = i;for(int i = m; i >= 1; i--) {for(int j = 1; j <= n; j++) PR[i][j] = PR[i + 1][j];int p1 = find(PR[i], L[i]), p2 = find(PR[i], R[i]);if(p1 != p2) PR[i][p2] = p1;}
}int solve(int l, int r) {for(int i = 1; i <= n; i++) tp[i] = PL[l][i];for(int i = 1; i <= n; i++) {int u = i, v = PR[r][i];int p1 = find(tp, u), p2 = find(tp, v);if(p1 != p2) tp[p2] = p1;}int ret = 0;for(int i = 1; i <= n; i++) {if(i == find(tp, i)) ret++;}return ret;
}int main() {//FIN;while(~scanf("%d%d", &n, &m)) {for(int i = 1; i <= m; i++) {scanf("%d%d", &L[i], &R[i]);}presolve();int Q, l, r;scanf("%d", &Q);while(Q--) {scanf("%d%d", &l, &r);printf("%d\n", solve(l - 1, r + 1));}}return 0;
}