【LOJ#2162】【POI2011】Garbage（欧拉回路）

题面

题解

首先有一个比较显然的结论，对于不需要修改颜色的边可以直接删掉，对于需要修改的边保留。说白点就是每条边要被访问的次数可以直接模二。证明的话就是如果一条边被经过了两次，证明其连通了两侧的两个块，那么把这两次删掉，可以把两侧各拆分成一个欧拉回路，不会影响答案。

于是剩下的边直接对于每一个连通块算欧拉回路。

然后对于强制定向之后的图直接\(dfs\)找到所有简单环就可以了。

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m;

int f[MAX];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

struct Line{int v,next;}e[MAX*20];

int h[MAX],cnt=2,dg[MAX],cur[MAX];

void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;dg[v]++;}

bool vis[MAX*10];int dir[MAX*10];

vector<int> Ans[MAX];int tot;

void dfs(int u)

{

	for(int &i=cur[u];i;i=e[i].next)

	{

		if(vis[i>>1])continue;int j=i;

		vis[i>>1]=true;dfs(e[i].v);

		dir[j>>1]=j&1;

	}

}

int St[MAX],top;bool inq[MAX];

void DFS(int u)

{

	St[++top]=u;inq[u]=true;

	for(int &i=h[u];i;i=e[i].next)

	{

		if(!inq[u])return;

		int v=e[i].v;if((i&1)!=dir[i>>1])continue;

		if(inq[v])

		{

			int p;++tot;Ans[tot].push_back(v);

			do{p=St[top--];Ans[tot].push_back(p);inq[p]=false;}while(p!=v);

			St[++top]=v;inq[v]=true;

		}

		else DFS(v);

	}

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)f[i]=i;

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

	{

		int u=read(),v=read(),s=read(),t=read();

		if(s^t)Add(u,v),Add(v,u),f[getf(u)]=getf(v);

	}

	for(int i=1;i<=n;++i)if(dg[i]&1){puts("NIE");return 0;}

	for(int i=1;i<=n;++i)cur[i]=h[i];

	for(int i=1;i<=n;++i)if(getf(i)==i)dfs(i);

	for(int i=1;i<=n;++i)DFS(i);

	printf("%d\n",tot);

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

	{

		printf("%d ",(int)Ans[i].size()-1);

		for(int u:Ans[i])printf("%d ",u);puts("");

	}

	return 0;

}

巴特西

【LOJ#2162】【POI2011】Garbage（欧拉回路）

【LOJ#2162】【POI2011】Garbage（欧拉回路）

题面

题解

最新文章

热门文章