啊哈磊_编程从这里起步
标题:
vgjkhyk
[打印本页]
作者:
渣男.
时间:
2018-12-2 17:20
标题:
vgjkhyk
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> e[5001];
int n,m,book[5001]={0},num[5001],p[5001],q[5001],ans[50001]={0};
int cnt=0,neverP,neverQ;
void dfs(int u)
{
if(book[u]==1) return;
book[u]=1;
cnt++;
num[cnt]=u;
//printf("%d ",u);
for(int i=0;i<e[u].size();i++)
{
dfs(e[u][i]);
}
return ;
}
void dfs2(int u)
{
if(book[u]==1) return;
book[u]=1;
cnt++;
num[cnt]=u;
//printf("%d ",u)P
for(int i=0;i<e[u].size();i++)
{
int v;
v=e[u][i];
if(!(u==neverP && v==neverQ) && !(v==neverP && u==neverQ))
dfs2(v);
}
return ;
}
int main()
{
//memset(ans,0x3F,sizeof(ans));
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int x,y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
p[i]=x;
q[i]=y;
}
//sort 使其所有的点从小到大
for(int i=1;i<=n;i++)
{
sort(e[i].begin(),e[i].end());
}
if(m==n-1)
{
dfs(1);
for(int k=1;k<=n;k++)
printf("%d ",num[k]);
}
else
{
for(int i=1;i<=m;i++)
{
memset(book,0,sizeof(book));
memset(num,0,sizeof(num));
cnt=0;
neverP=p[i];neverQ=q[i];
dfs2(1);
if(cnt==n)
{
if(ans[1]==0)
{
for(int j=1;j<=n;j++)
{
ans[j]=num[j];
}
}
else
{
//字典
//num 1 3 2 4 5 6
//ans 1 3 2 5 4 6
for(int j=1;j<=n;j++)
{
if(ans[j]==num[j])
continue;
else if (num[j]>ans[j])
break;
else if(num[j]<ans[j])
{
for(int k=1;k<=n;k++)
{
ans[k]=num[k];
}
for(int k=1;k<=n;k++)
printf("%d ",ans[k]);
printf("\n");
break;
}
}
}
}
}
/*
for(int k=1;k<=n;k++)
printf("%d ",ans[k]);
*/
}
return 0;
}
复制代码
欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)
Powered by Discuz! X3.2