AtCoder ABC #366 : G - XOR Neighbors

ちょっと手間取ったけど、その後はすんなり解けた。
https://atcoder.jp/contests/abc366/tasks/abc366_g

問題

無向グラフが与えられる。
各点vに1以上2^60未満の整数X[v]を割り振り、各点について隣接点に割り振られた整数値のxorが0となるようにせよ。

解法

まず各点に0/1を割り振ることを考える。
各点vに割り振る値をA[v]とすると、各点vの隣接点の集合N(v)に対し、でなければいけない。
この式をN個並べ、掃き出し法で解けばいいのだが、このままだと全変数0で成り立ってしまう。

そこで、強制的に1を割り当てたい頂点vを一つ選び、A[v]=1という式を追加しよう。
そうすると、A[v]=1という条件を満たしたうえで他頂点の0/1を定めることができる。

N≦60であることを考えると、解はもうすぐ。
上記掃き出し法をN回行い、A[v] = 1としたときに同じく1とすべき点集合が定まったとする。
その場合、それらの点uに対し、X[u]に2^vを加算すればよい。

言い換えると、N回方程式を解くうち、最低1回は自頂点が非ゼロの回を設けるということになる。

int N,M;
vector<int> E[60];
ll ret[66];

const int MAT=64;
bitset<64> BS[645];
int V[64],R[64];

int Gauss(int R,int C,bitset<MAT> BS[MAT],int v[MAT],int r[MAT]) {
	int i,j,k;
	int nex=0;
	FOR(i,R) {
		while(nex<C) {
			for(j=i;j<R;j++) if(BS[j][nex]) break;
			if(j!=R) break;
			nex++;
		}
		if(nex>=C) break;
		swap(BS[i],BS[j]);
		swap(v[i],v[j]);
		FOR(j,R) if(i!=j && BS[j][nex]) {
			v[j]^=v[i];
			BS[j]^=BS[i];
		}
		nex++;
	}
	FOR(i,C) r[i]=0;
	int num=0;
	FOR(i,R) {
		
		FOR(j,C) if(BS[i][j]) break;
		if(j<C) {
			r[j]=v[i];
			num++;
		}
		else if(v[i]) {
			return -1;
		}
	}
	
	return num;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	FOR(i,N) {
		ZERO(V);
		FOR(x,N) {
			BS[x].reset();
			FORR(e,E[x]) BS[x][e]=1;
		}
		BS[N].reset();
		BS[N][i]=1;
		V[N]=1;
		x=Gauss(N+1,N,BS,V,R);
		if(x==-1) {
			cout<<"No"<<endl;
			return;
		}
		FOR(x,N) {
			if(R[x]) ret[x]|=1LL<<i;
		}
	}
	
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<ret[i]<<" ";
	cout<<endl;
	
}

まとめ

ちょっと計算量心配だったけど全然問題なかったね。