BZOJ 3563 DZY Loves Chinese / BZOJ 3569 DZY Loves Chinese II 隨機化+高斯消元解異或方程組

題目大意：給出一個無向圖，問刪掉k條邊的時候，圖是否聯通。

思路：雖然我把這兩個題放在了一起，但是其實這兩個題可以用完全不同的兩個解法來解決。

第一個題其實是DZY出錯了。。。把每次的邊數也異或了，那就直接用這個性質一個一個往後推就行了。。最後一個暴力求一下。。

第二個題才是本意啊。

聽到做法的時候我驚呆了。。

首先是將整個圖中拆出一個樹，那麼所有邊就分為樹邊和非樹邊。將所有非樹邊都加一個隨機權值。樹邊的權值是所有能夠覆蓋它的非樹邊的權值的異或和。

把整個圖拆開的充要條件是拆掉一條樹邊，同時將所有覆蓋它的非樹邊也要拆掉，這些邊的異或和正好等於0.這個就可以用高斯消元解異或方程組來解決了。

神啊神啊神啊神啊。。。

CODE：

#include 
#include 
#include 
#include 
#define MAX 1000010
using namespace std;

struct Edge{
	int x,y,len;
	bool tree_edge;
	
	void Read() {
		scanf("%d%d",&x,&y);
	}
}edge[MAX];

int points,edges,asks;
int head[MAX],total = 1;
int next[MAX],aim[MAX];

bool v[MAX];
int _xor[MAX];

inline void Add(int x,int y)
{
	next[++total] = head[x];
	aim[total] = y;
	head[x] = total;
}

void BuildTree(int x,int last)
{
	v[x] = true;
	for(int i = head[x]; i; i = next[i])
		if(!v[aim[i]]) {
			edge[i >> 1].tree_edge = true;
			BuildTree(aim[i],x);
		}
}

void DFS(int x,int last)
{
	for(int i = head[x]; i; i = next[i])
		if(edge[i >> 1].tree_edge && aim[i] != last) {
			DFS(aim[i],x);
			edge[i >> 1].len = _xor[aim[i]];
			_xor[x] ^= _xor[aim[i]];
		}
}

int temp[MAX];

inline bool GaussElimination(int cnt)
{
	int k = 0,i;
	for(int j = 1 << 30; j; j >>= 1) {
		for(i = k + 1; i <= cnt; ++i)
			if(temp[i]&j)
				break;
		if(i == cnt + 1)	continue;
		swap(temp[i],temp[++k]);
		for(int i = 1; i <= cnt; ++i)
			if(temp[i]&j && i != k)
				temp[i] ^= temp[k];
	}
	return temp[cnt];
}

int main()
{
	srand(19970815);
	cin >> points >> edges;
	for(int i = 1; i <= edges; ++i) {
		edge[i].Read();
		Add(edge[i].x,edge[i].y);
		Add(edge[i].y,edge[i].x);
	}
	BuildTree(1,0);
	for(int i = 1; i <= edges; ++i)
		if(!edge[i].tree_edge) {
			edge[i].len = rand();
			_xor[edge[i].x] ^= edge[i].len;
			_xor[edge[i].y] ^= edge[i].len;
		}
	DFS(1,0);
	cin >> asks;
	int last_ans = 0;
	for(int cnt,x,i = 1; i <= asks; ++i) {
		scanf("%d",&cnt);
		//cnt ^= last_ans;
		for(int j = 1; j <= cnt; ++j) {
			scanf("%d",&x);
			x ^= last_ans;
			temp[j] = edge[x].len;
		}
		bool flag = !GaussElimination(cnt);
		if(!flag) {
			puts("Connected");
			++last_ans;
		}
		else	puts("Disconnected");
	}
	return 0;
}