【dfs】bzoj3563 DZY Loves Chinese

因为我们可以通过把某一行读到末尾来获取真正的K，所以把它和假K异或之后就是之前联通的次数(异或的逆运算为其本身)。最后一次的暴力一下。

#include<cstdio>

#include<cstring>

using namespace std;

#define N 100001

#define M 500001

int n,m,K,q,ans;

char s[1001];

bool del[M<<1];

int en,v[M<<1],first[N],next[M<<1],bs[20];

void AddEdge(int U,int V)

{

	v[++en]=V;

	next[en]=first[U];

	first[U]=en;

}

bool vis[N];

int cnt,RealK;

void dfs(int U)

{

	vis[U]=1; ++cnt;

	for(int i=first[U];i;i=next[i])

	  if((!vis[v[i]])&&(!del[i]))

	    dfs(v[i]);

}

int main()

{

	int A,B;

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;++i)

	  {

	  	scanf("%d%d",&A,&B);

	  	AddEdge(A,B);

	  	AddEdge(B,A);

	  }

	scanf("%d",&q);

	for(int i=1;i<q;++i)

	  {

	  	scanf("%d",&K);

		RealK=0;

		gets(s);

		int len=strlen(s);

		for(int j=0;j<len;++j)

		  if(s[j]==' ')

		    ++RealK;

		if(i!=1)

		  {

		  	if((K^RealK)>ans) puts("Connected");

			else puts("Disconnected");

		  }

		ans=(K^RealK);

	  }

	scanf("%d",&K);

	RealK=0;

	while(scanf("%d",&bs[++RealK])!=EOF);

	if((K^(RealK-1))>ans) puts("Connected");

	else puts("Disconnected");

	ans=(K^(RealK-1));

	for(int i=1;i<RealK;++i)

	  del[((bs[i]^ans)<<1)-1]=del[(bs[i]^ans)<<1]=1;

	dfs(1);

	puts(cnt==n?"Connected":"Disconnected");

	return 0;

}