双圈覆盖

C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 1100K, 提交时间: 2020-02-02 11:29:06

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<assert.h>
#include<set>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<iostream>
#include<bitset>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define rep(i,j,k) for(int i=(int)(j);i<=(int)(k);i++)
#define per(i,j,k) for(int i=(int)(j);i>=(int)(k);i--)
using namespace std;
typedef long long LL;
typedef double db;
const int N=505;
int n,m;
pii go[N][N];
vector<vector<int> >way;
int num[N];
bool vis[N][N];
pii getaft(int x,int d){
	if(d!=num[x])return pii(x,d+1);
	if(x==n)return pii(1,1);
	return pii(x+1,1);
}
pii getpre(int x,int d){
	if(d!=1)return pii(x,d-1);
	if(x==1)return pii(n,num[n]);
	return pii(x-1,num[x-1]);
}
vector<int> d;
int kd[N][N];
void pbd(int x){
	if(d.size())if(d[d.size()-1]==x)return;
	d.pb(x);
}
pii FL;
void dfs(int x,int y,int md){
	vis[x][y]=1;
	pbd(x);
	if(kd[x][y]==md){
		//go right
		pii w=getaft(x,y);
		pbd(w.fi);
		while(w.se==1){
			w=getaft(w.fi,w.se);
			pbd(w.fi);
		}
		x=w.fi;
		y=w.se;
		pbd(x);
		assert(vis[x][y]==0);
		vis[x][y]=1;

		w=go[x][y];
		x=w.fi;
		y=w.se;
		if(vis[x][y]){
			FL=pii(x,y);
			return;
		}
		pbd(x);
		vis[x][y]=1;
		dfs(x,y,md);
	}
	else{
		pii w=getpre(x,y);
		pbd(w.fi);
		while(w.se==1){
			w=getpre(w.fi,w.se);
			pbd(w.fi);
		}
		x=w.fi;
		y=w.se;
		pbd(x);
		assert(vis[x][y]==0);
		vis[x][y]=1;

		w=go[x][y];
		x=w.fi;
		y=w.se;
		if(vis[x][y]){
			FL=pii(x,y);
			return;
		}
		pbd(x);
		vis[x][y]=1;
		dfs(x,y,md);
	}
}
void Main(){
	scanf("%d%d",&n,&m);
	assert(4<=n&&n<=50);
	assert(n<=m&&m<=500);
	rep(i,1,n)rep(j,1,m)go[i][j]=pii(0,0);
	rep(i,1,n)num[i]=1;
	way.clear();
	memset(vis,0,sizeof vis);
	rep(i,1,m){
		int a,b;scanf("%d%d",&a,&b);
		assert(a<b);
		assert(!vis[a][b]);
		vis[a][b]=1;

		if(a+1==b)continue;
		if(a==1&&b==n)continue;
		num[a]++;num[b]++;
		go[a][num[a]]=pii(b,num[b]);
		go[b][num[b]]=pii(a,num[a]);
	}
	d.clear();rep(i,1,n)d.pb(i);way.pb(d);
	d.clear();

	int now=0;
	rep(i,1,n)rep(j,2,num[i]){
		now^=1;kd[i][j]=now;
	}
	memset(vis,0,sizeof vis);

	rep(i,1,n)rep(j,2,num[i])if(!vis[i][j]){
		d.clear();
		dfs(i,j,1);
		while(d[0]==d[d.size()-1])d.pop_back();
		way.pb(d);
		assert(FL==pii(i,j));
	}
	memset(vis,0,sizeof vis);
	rep(i,1,n)rep(j,2,num[i])if(!vis[i][j]){
		d.clear();
		dfs(i,j,0);
		while(d[0]==d[d.size()-1])d.pop_back();
		way.pb(d);
		assert(FL==pii(i,j));
	}
	printf("%d\n",way.size());
	for(auto t:way){
		printf("%d ",t.size());
		for(int x:t)printf("%d ",x);puts("");
	}
}
int main(){
	int t;scanf("%d",&t);
	while(t--)Main();
	return 0;
}

C++ 解法, 执行用时: 20ms, 内存消耗: 1720K, 提交时间: 2021-09-20 16:52:33

#include<bits/stdc++.h>
using namespace std;
const int N = 1050+5;
const int M = 55;

int T;
int n,m;
int pre[N],nex[N];
bool e[N][N],vis[2][M][M],use[M];
vector<int>g[2][M],ans[N];
int q[N];

bool dfs(bool t,int x){
	q[++q[0]]=x;
	for(int i=0;i<g[t][x].size();++i){
		int y=g[t][x][i];
		if(vis[t][x][y])continue;
		vis[t][x][y]=vis[t][y][x]=1;
		dfs(t,y);
		return 1;
	}
	return 0;
}

int main(){
	//freopen("c.in","r",stdin);
	//freopen("c.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		memset(e,0,sizeof(e));
		memset(vis,0,sizeof(vis));
		memset(pre,0,sizeof(pre));
		memset(nex,0,sizeof(nex));
		memset(use,0,sizeof(use));
		for(int i=1;i<=n;++i){
			nex[i]=i+1;
			pre[i]=i-1;
			for(int j=0;j<2;++j){
				g[j][i].clear();
			}
		}
		nex[n]=1;
		pre[1]=n;
		for(int i=1,x,y;i<=m;++i){
			scanf("%d%d",&x,&y);
			e[x][y]=1;
			e[y][x]=1;
			for(int j=0;j<2;++j)
			if(x!=pre[y]&&y!=pre[x]){
				g[j][x].push_back(y);
				g[j][y].push_back(x);
				//cout<<j<<" "<<x<<" "<<y<<endl;
			}
		}
		m=n;
		for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		if(e[i][j]){
			if(j==pre[i]||j==nex[i])continue;
			if(!use[i]){
				use[i]=1;
				continue;
			}
			int x=++m,y=nex[i];
			e[i][y]=e[y][i]=0;
			e[i][x]=e[x][i]=1;
			e[x][y]=e[y][x]=1;
			nex[i]=x;nex[x]=y;
			pre[x]=i;pre[y]=x;
			e[i][j]=e[j][i]=0;
			e[x][j]=e[j][x]=1;
		}
		for(int x=1,c=0;;x=nex[x],c^=1){
			if(x<=n){
				int y=(x==1?n:x-1);
				g[c][x].push_back(y);
				g[c][y].push_back(x);
				//cout<<c<<" "<<x<<" "<<y<<endl;
			}
			if(nex[x]==1)break;
		}
		int tot=1;
		for(int i=1;i<=n;++i)ans[tot].push_back(i);
		for(int j=0;j<2;++j){
			for(int i=1;i<=n;++i){
				q[0]=0;
				while(dfs(j,i)){
					++tot;
					for(int j=1;j<q[0];++j){
						ans[tot].push_back(q[j]);
					}
					q[0]=0;
				}
			}
		}
		printf("%d\n",tot);
		for(int i=1;i<=tot;++i){
			printf("%d ",ans[i].size());
			for(int j=0;j<ans[i].size();++j){
				printf("%d ",ans[i][j]);
			}
			printf("\n");
			ans[i].clear();
		}
	}
}
/*
1
6 10
1 2
2 3
3 4
4 5
5 6
6 1
1 5
2 5
3 5
4 6
*/

详情