JZOJ3453. 【NOIP2013中秋节模拟】连通块(connect)-布布扣-bubuko.com

　　你应该知道无向图的连通块的数量，你应该知道如何求连通块的数量。当你兴奋与你的成就时，破坏王Alice拆掉了图中的边。当她发现，每删去一条边，你都会记下边的编号，同时告诉她当前连通块的个数。
　　然而，对边编号简直就是个悲剧，因为Alice为了刁难你，拆掉编号从l到r的边，当然你需要做的事情就是求连通块的个数。如果你答对了，Alice会把拆掉的边装好，迚行下一次破坏。如果你无法完成这个任务，Alice会彻底毁了你的图。
　　进行完足够多次之后，Alice觉得无聊，就玩去了，而你却需要继续做第三题。

Input

　　第一行两个整数n,m，表示点数和边数。
　　之后m行每行两个整数x,y，表示x与y之间有无向边。（按读入顺序给边编号，编号从1开始）。
　　 一行一个整数k，表示Alice的破坏次数。
　　之后k行，每行两个整数l,r。

Output

　　k行，每行一个整数。

Solution

　　用 $f_{i}$

　　用 $g_{i}$

$g_{i}$

 1 var
 2   n,m,k,ans:longint;
 3   fa:array [0..501] of longint;
 4   x,y:array [0..10001] of longint;
 5   fa1,fa2:array [0..10001,0..501] of longint;
 6 function get1(y,x:longint):longint;
 7 begin
 8   if fa1[y,x]=x then exit(x);
 9   fa1[y,x]:=get1(y,fa1[y,x]);
10   exit(fa1[y,x]);
11 end;
12 
13 function get2(y,x:longint):longint;
14 begin
15   if fa2[y,x]=x then exit(x);
16   fa2[y,x]:=get2(y,fa2[y,x]);
17   exit(fa2[y,x]);
18 end;
19 
20 procedure init;
21 var
22   i,l,r,t1,t2:longint;
23 begin
24   readln(n,m);
25   for i:=1 to m do
26     readln(x[i],y[i]);
27   for i:=1 to n do
28     begin
29       fa1[0,i]:=i;
30       fa2[m+1,i]:=i;
31     end;
32   for i:=1 to m do
33     begin
34       l:=i; fa1[l]:=fa1[l-1];
35       t1:=get1(l,x[l]);
36       t2:=get1(l,y[l]);
37       fa1[l,t2]:=t1;
38       r:=m-i+1; fa2[r]:=fa2[r+1];
39       t1:=get2(r,x[r]);
40       t2:=get2(r,y[r]);
41       fa2[r,t2]:=t1;
42     end;
43 end;
44 
45 function get(x:longint):longint;
46 begin
47   if fa[x]=x then exit(x);
48   fa[x]:=get(fa[x]);
49   exit(fa[x]);
50 end;
51 
52 procedure main;
53 var
54   i,j,l,r,t1,t2,t3:longint;
55 begin
56   readln(k);
57   for i:=1 to k do
58     begin
59       readln(l,r);
60       fa:=fa1[l-1];
61       for j:=1 to n do
62         begin
63           t1:=get(j);
64           t2:=get(get2(r+1,j));
65           fa[t2]:=t1;
66         end;
67       ans:=0;
68       for j:=1 to n do
69         if get(fa[j])=j then inc(ans);
70       writeln(ans);
71     end;
72 end;
73 
74 begin
75   assign(input,‘connect.in‘);
76   assign(output,‘connect.out‘);
77   reset(input);
78   rewrite(output);
79   init;
80   main;
81   close(input);
82   close(output);
83 end.

JZOJ3453. 【NOIP2013中秋节模拟】连通块(connect)

Description

Input

Output

Solution