64pts,求HACK
查看原帖
64pts,求HACK
934048
ni_ju_ge楼主2024/9/26 20:58
#include<iostream>
using namespace std;
int g[1001][1001],n,m,x,y,b[501],v[1001];
bool pk(int t,int s)
{
	for(int i=1;i<s;i++)
	{
// 		cout<<t<<" "<<i<<" "<<b[i]<<" "<<g[t][b[i]]<<endl;
		if(g[t][b[i]]==1&&not(i==1&&s>=3&&g[t][b[i]]>=1))return false;
	}
	return true;
}
void dfs(int k,int s,int q)
{
	b[s]=k;
	if(s>=4&&g[k][q]>=1)
	{
		y=1;
		for(int i=1;i<=s;i++)cout<<b[i]<<" ";
		return;
	}
	if(s>=4&&k==q)
	{
		y=1;
		for(int i=1;i<=s;i++)cout<<b[i]<<" ";
		return;
	}
	for(int i=1;i<=n;i++)
	{
// 		cout<<k<<endl;
		if(g[k][i]==1&&v[i]==0&&pk(i,s))
		{
			g[k][i]=0;g[i][k]=0;v[k]=1;
			dfs(i,s+1,q);
			g[k][i]=1;g[i][k]=1;v[k]=0;
			if(y==1)return;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		g[x][y]=1;g[x][0]++;
		g[y][x]=1;g[y][0]++;
	}
	x=1;y=0;
	for(int i=2;i<=n;i++)
	{
		if(g[i][0]>=g[x][0])x=i;
	}
	dfs(x,1,x);
	int xx=1;
	if(x==1)xx=2;
	if(y==1)
	{
		for(int i=1;i<=n;i++)
		{
			if(g[i][0]<g[x][0]&&g[i][0]>=g[xx][0])xx=i;
		}
		dfs(xx,1,xx);
	}
	if(y==0)cout<<"no";
}
2024/9/26 20:58
加载中...