1 条题解
-
0
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; int n, m, ans[5010], tot, a[5010], l[5010], sum, f[5010], to[5010],d; vector <int> v[5010]; bool flag; bool check(){ for(int i = 1;i <= n;i++) if(!a[i]) return 0; for(int i = 1;i <= n;i++) if(a[i] != ans[i]) return ans[i] > a[i]; } void dfs(int u, int fa){ if(sum > n){ flag = 1; return; } a[sum] = u; for(int i = 0; i < v[u].size(); i++){ if((u == f[d] && v[u][i] == to[d]) || (v[u][i] == f[d] && u == to[d]) || v[u][i] == fa) continue; sum++; dfs(v[u][i], u); } } int main(){ memset(ans, 60, sizeof(ans)); cin >> n >> m; for(int i = 1; i <= m; i++){ int x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); f[i] = x; to[i] = y; } for(int i = 1;i <= n;i++) sort(v[i].begin(),v[i].end()); if(m == n - 1){ sum = 1; dfs(1, 0); memcpy(ans, a, sizeof(a)); }else if(m == n){ for(int i = 1; i <= m; i++){ memset(a, 0, sizeof(a)); d = i; sum = 1; flag = 0; dfs(1, 0); if(!flag && check()) memcpy(ans, a, sizeof(a)); } } for(int i = 1; i <= n; i++) cout << ans[i] << ' ' ; return 0; }
- 1
信息
- ID
- 404
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 2
- 已通过
- 2
- 上传者