题目分析

看了这道题的题目,感觉好难啊,不可做啊,那么我们就要找一些特殊的性质。注意到:

每行第一个数K而后K个编号c1~cK:表示K条边,编号为c1~cK
为了体现在线,K以及c1~cK均需异或之前回答为连通的个数

诶……

所以,把一行读进来,查看这一行有多少个数,从而得到之前回答为连通的个数,然后就获得了上一个询问的答案。对于最后一个询问,我们直接用并查集维护一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
struct edges{int x,y;}e[500005];
char s[1005];
int n,m,q,blk,f[100005],ans[100005],v[500005];
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
int main()
{
    int k,js;
    scanf("%d%d",&n,&m);
    for(RI i=1;i<=m;++i) scanf("%d%d",&e[i].x,&e[i].y);
    scanf("%d",&q);
    for(RI i=1;i<=q;++i) {
        scanf("%d",&k),gets(s+1),js=0;
        int len=strlen(s+1);
        for(RI j=1;j<=len;++j)
            if(isdigit(s[j])&&!isdigit(s[j+1])) ++js;
        ans[i]=js^k;
    }
    for(RI i=1;i<q;++i)
        if(ans[i+1]==ans[i]) puts("Disconnected");
        else puts("Connected");
    k=0,s[0]='a';
    int len=strlen(s+1);
    for(RI i=1;i<=len;++i) {
        if(isdigit(s[i])) k=k*10+s[i]-'0';
        else if(isdigit(s[i-1])) v[k^ans[q]]=1,k=0;
       }
    v[k^ans[q]]=1;
    blk=n;for(RI i=1;i<=n;++i) f[i]=i;
    for(RI i=1;i<=m;++i)
        if(!v[i]) {
            int r1=find(e[i].x),r2=find(e[i].y);
            if(r1!=r2) --blk,f[r1]=r2;
        }
    if(blk==1) puts("Connected");
    else puts("Disconnected");
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

1 条评论

konnyakuxzy · 2018年3月30日 8:33 下午

Orz
还有这种操作
赶紧膜Orz%%%%%

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *