[POI2011]Śmieci

题目大意：

一个\(n(n\le10^5)\)个点\(m(m\le10^6)\)条边的无向图，每条边有边权\(0/1\)，试找出若干个环，使得每次翻转环上所有边的权值，使得最后所有边权都是\(0\)。

思路：

权值为\(0\)的边都没有用，因为若方案存在，一定存在一种方案使得所有环只经过\(1\)边。

因此我们只留下\(1\)边，暴力DFS找环即可。注意要加上当前弧优化。

源代码：

#include<stack>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=1e5+1,M=2e6;

int deg[N],h[N];

bool mark[M],ins[N];

struct Edge {

	int to,next;

};

Edge e[M];

inline void add_edge(const int &u,const int &v) {

	e[++h[0]]=(Edge){v,h[u]};h[u]=h[0];deg[u]++;

	e[++h[0]]=(Edge){u,h[v]};h[v]=h[0];deg[v]++;

}

std::stack<int> stk;

std::vector<std::vector<int> > ans;

void dfs(const int &x) {

	if(ins[x]) {

		const int k=ans.size();

		ans.resize(k+1);

		int y;

		do {

			y=stk.top();

			stk.pop();

			ins[y]=false;

			ans[k].push_back(y);

		} while(y!=x);

	}

	for(int &i=h[x];~i;i=e[i].next) {

		const int &y=e[i].to;

		if(mark[i]) continue;

		mark[i]=mark[i^1]=true;

		stk.push(x);

		ins[x]=true;

		dfs(y);

	}

}

int main() {

	memset(h,-1,sizeof h);

	const int n=getint(),m=getint();

	for(register int i=0;i<m;i++) {

		const int u=getint(),v=getint();

		if(getint()^getint()) {

			add_edge(u,v);

		}

	}

	for(register int i=1;i<=n;i++) {

		if(deg[i]%2==1) {

			puts("NIE");

			return 0;

		}

	}

	for(register int i=1;i<=n;i++) {

		dfs(i);

	}

	printf("%lu\n",ans.size());

	for(register unsigned i=0;i<ans.size();i++) {

		printf("%lu ",ans[i].size());

		for(register unsigned j=0;j<ans[i].size();j++) {

			printf("%d ",ans[i][j]);

		}

		printf("%d\n",ans[i][0]);

	}

	return 0;

}