2015
09-17

# Query on Graph

Given an undirected and connected graph with n vertices and m edges, and q queries on the graph. In each query, you are given two integers l, r, and output the number of connected components of the graph only with vertices labelled from l to r (that means deleting the vertices labelled 1, 2, …, l-1, r+1, r+2, … , n and the corresponding edges from the graph, then output the number of connected components).

The first line of the input contains an integer T (T<=10), indicating the number of test cases.
For each test case, the first line contains two integers n, m (1<=n<=30000, n-1<=m<=3*n), as described above.
For next m lines, each line contains two integers u, v (1<=u, v<=n), indicates there is an edge between vertex u and vertex v.
Next line is an integer q(1<=q<=30000), indicates the number of queries.
For next q lines, each line contains two integers l, r (1<=l<=r<=n), indicates the query.
The graph are generated randomly and there are only few big datas.

The first line of the input contains an integer T (T<=10), indicating the number of test cases.
For each test case, the first line contains two integers n, m (1<=n<=30000, n-1<=m<=3*n), as described above.
For next m lines, each line contains two integers u, v (1<=u, v<=n), indicates there is an edge between vertex u and vertex v.
Next line is an integer q(1<=q<=30000), indicates the number of queries.
For next q lines, each line contains two integers l, r (1<=l<=r<=n), indicates the query.
The graph are generated randomly and there are only few big datas.

1
9 10
1 2
1 3
2 4
2 5
4 5
3 6
3 7
6 9
8 9
8 7
4
1 2
3 5
6 9
6 7

Case #1:
1
2
1
2

1.区间划分： 对于l~r的每一个区间询问，最暴力的方法是从l到r一个一个的计算过去，复杂度为O(q*n)，对于询问数q=3w，区间长度n=3w的题，必须超时，那么考虑优化。

2.连通块数量的维护：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define clr(a,b) memset(a,b,sizeof(a))
typedef long long lld;
const int INF = ~0u>>1;

const int MAXN = 30010;
struct Edge {
int v, next;
}g[MAXN*10];
int n,m,nq;
struct Q {
int l, r, id;
int b;
bool operator < (const Q &tt) const {
if(b == tt.b) return r < tt.r;
return b < tt.b;
}
}q[MAXN];
int ans[MAXN];
int fa[MAXN];
int L,R;
int vis[MAXN];
int tfa[MAXN];
int block_size;
int rcnt;
int now;

int Find(int x) {
return fa[x] = (fa[x] == x) ? x : Find(fa[x]);
}

int merge(int a, int b) {
a = Find(a);    b = Find(b);
if(a == b) return 0;
fa[a] = b;
return 1;
}

int Tfind(int x) {
if(vis[x] != now) {
tfa[x] = fa[x];
vis[x] = now;
}
return tfa[x] = (tfa[x] == x) ? x : Tfind(tfa[x]);
}

int Tmerge(int a, int b) {
a = Tfind(a);   b = Tfind(b);
if(a == b) return 0;
tfa[a] = b;
return 1;
}

int work(int l, int r, int ss) {
if(ss != L/block_size - 1) {
L = (ss+1) * block_size;
rcnt = 0;
R = L+1;
for(int i=L-block_size+1; i<=L; i++) fa[i] = i;
}
for(; R<=r; R++) {
fa[R] = R;
rcnt ++;
for(int p=head[R]; ~p; p=g[p].next) {
int v = g[p].v;
if(v >= R || v <= L) continue;
if(merge(R,v)) rcnt --;
}
}
int tr = min(r,L);
int ret = 0;
if(r>L) ret += rcnt;
for(int i=l; i<=tr; i++) {
ret ++;
for(int p=head[i]; ~p; p=g[p].next) {
int v = g[p].v;
if(v<=i || v>r) continue;
if(Tmerge(i,v)) ret --;
}
}
return ret;
}

void add_edge(int a, int b) {
g[tot].v = b;
head[a] = tot ++;
}

int main() {
int cas, ca = 0;
scanf("%d", &cas);
while(cas--) {
tot = 0;
scanf("%d%d", &n, &m);
int a,b;
REP(i,0,m) {
scanf("%d%d", &a, &b);
}
scanf("%d", &nq);
block_size = (int)sqrt(n*1.0);
REP(i,0,nq) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].b = q[i].l/block_size;
q[i].id = i;
}
sort(q,q+nq);
L = R = -1;
clr(vis,-1);
REP(i,0,nq) {
now = i;
ans[q[i].id] = work(q[i].l,q[i].r,q[i].b);
}
printf("Case #%d:\n", ++ca);
REP(i,0,nq) printf("%d\n", ans[i]);
}
return 0;
}