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为了体现在线,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
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13
Sample Output
Connected
Connected
Connected
Connected
Disconnected
解题思路:
考虑到将原图不连通必须切断一个点的所有联通方式
那么可以想到用一种方式来使多个元素互相抵消。
这些元素就是连同一个点的所有边。
那么使这些遍抵消的方式就是让一条边与其他异或和为0
这就需要线性无关组了。
Dfs出一颗树。
将非树边的每一条边rand上一个权值,
那么这条边能做出贡献的位置就是Dfs树上祖先的位置。
那么就向上更新,在树边处的答案就是后面相关边的异或和
最后在查询时暴力插入线性无关组中,
若出现异或和为0的情况就是所有相关的边都被删除了。
就是不连通了。
代码:
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
void ade(int f,int t,int no);
typedef long long lnt;
struct pnt{
int hd;
int fa;
lnt val;
}p[];
struct ent{
int twd;
int lst;
int blg;
}e[];
struct edge{
int f,t;
lnt val;
bool vis;
void Insert(int no)
{
scanf("%d%d",&f,&t);
ade(f,t,no);
ade(t,f,no);
}
}ede[];
lnt b[];
int n,m;
int cnt;
int Q;
int lstans;
void ade(int f,int t,int no)
{
cnt++;
e[cnt].twd=t;
e[cnt].blg=no;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void B_(int x,int f)
{
p[x].fa=f;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].fa)continue;
ede[e[i].blg].vis=true;
B_(to,x);
}
return ;
}
void C_(int x,int f)
{
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].fa==x);else continue;
C_(to,x);
ede[e[i].blg].val^=p[to].val;
p[x].val^=p[to].val;
}
return ;
}
bool Insert(lnt x)
{
for(int i=;i>=;i--)
{
if(x&(1ll<<i))
{
if(b[i]==)
{
b[i]=x;
return true;
}else x^=b[i];
}
}
if(!x)return false;
return true;
}
int main()
{
// freopen("a.in","r",stdin);
srand(time(NULL));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)ede[i].Insert(i);
B_(,);
for(int i=;i<=m;i++)
{
if(ede[i].vis)continue;
ede[i].val=rand()+;
p[ede[i].f].val^=ede[i].val;
p[ede[i].t].val^=ede[i].val;
}
C_(,);
scanf("%d",&Q);
while(Q--)
{
int k;bool flag=false;
scanf("%d",&k);
memset(b,,sizeof(b));
for(int i=;i<=k;i++)
{
int x;
scanf("%d",&x);x^=lstans;
if(!Insert(ede[x].val))flag=true;
}
if(flag)
{
puts("Disconnected");
}else{
puts("Connected");
lstans++;
}
}
return ;
}