3563: DZY Loves Chinese

Description
神校XJ之学霸兮，Dzy皇考曰JC。
摄提贞于孟陬兮，惟庚寅Dzy以降。
纷Dzy既有此内美兮，又重之以修能。
遂降临于OI界，欲以神力而凌♂辱众生。

今Dzy有一魞歄图，其上有N座祭坛，又有M条膴蠁边。
时而Dzy狂WA而怒发冲冠，神力外溢，遂有K条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。（可视为立即复原）
然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。
Input
第一行N,M
接下来M行x,y：表示M条膴蠁边，依次编号
接下来一行Q
接下来Q行：
每行第一个数K而后K个编号c1~cK：表示K条边，编号为c1~cK
为了体现在线，K以及c1~cK均需异或之前回答为连通的个数
Output
对于每个询问输出：连通则为‘Connected’，不连通则为‘Disconnected’
（不加引号）
Sample Input
5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13
Sample Output
Connected
Connected
Connected
Connected
Disconnected
HINT

HINT

N≤100000 M≤500000 Q≤50000 1≤K≤15

数据保证没有重边与自环

Tip：请学会使用搜索引擎

无聊写了这道伪在线题

因为我们通过计算这一行有多少个数字可以得到每次的k，xor之后得到以前说联通的次数，最后一个暴力并查集就行了

 const

     maxn=;

     maxm=;

 var

     x,y,e:array[..maxm]of longint;

     f:array[..maxn]of longint;

     n,m,q,last:longint;

 function find(x:longint):longint;

 begin

     if f[x]=x then exit(x);

     f[x]:=find(f[x]);

     exit(f[x]);

 end;

 procedure main;

 var

     i,cnt,k:longint;

 begin

     read(n,m);

     for i:= to m do

         read(x[i],y[i]);

     readln(q);readln;

     for i:= to q- do

         begin

             read(k);cnt:=;

             while not seekeoln do

                 begin

                     inc(cnt);

                     read(e[cnt]);

                 end;

             readln;

             k:=k xor cnt;

             if k>last then

                 writeln('Connected')

             else

                 writeln('Disconnected');

             last:=k;

         end;

     for i:= to cnt do e[i]:=e[i] xor k;

     for i:= to n do f[i]:=i;

     for i:= to cnt do y[e[i]]:=x[e[i]];

     for i:= to m do

         if find(x[i])<>find(y[i]) then f[f[x[i]]]:=f[y[i]];

     for i:= to n- do

         if find(i)<>find(i+) then

         begin

             writeln('Disconnected');

             exit;

         end;

     writeln('Connected');

 end;

 begin

     main;

 end.

巴特西

3563: DZY Loves Chinese - BZOJ

最新文章

热门文章