题目传送门！
NOIP好不容易的一道偏简单的题。
题目主要分两种情况： m = n - 1 和 m = n
对于第一种情况，我们直接用邻接矩阵，从1号点开始遍历，然后存下来即可。 60分get。
对于第二种情况，可以发现，无论我们怎么走，永远都会有一条边不会被用到。那么，这也就好办了。
我们只要每次枚举删掉一条边，然后跑一遍图，取字典序最小的一次即可。
但是，如果我们直接跑，时间复杂度表面上可行，但实际上由于一些常数，我们还是会TLE。
因此考虑优化：
首先，我们可以先跑一遍tarjan，然后就能知道图中的环。 如果这条删边不在环中，则会导致图不联通，无意义。因此可以略过。
其次，选择快读 + 邻接表跑图，而不是我们慢悠悠的 vector。
在加边前的排序时，我们还是可以选择vector，毕竟比较方便
#include <bits/stdc++.h> using namespace std; #define N 5010 inline int read(){ int x = 0; char c = getchar(); while(!isdigit(c)){ c = getchar(); } while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar(); } return x; } int n, m; int ans[N], cur[N], id = 0; namespace task1{ /*task1比较简单，直接矩阵遍历即可*/ int ma[5010][5010]; bool vis[N]; void dfs(int now){ for(int v = 1;v <= n; v++){ if(ma[now][v] && !vis[v]){ ans[++id] = v; vis[v] = 1; dfs(v); } } return ; } void main(){ for(int i = 1;i <= m; i++){ int x = read(), y = read(); ma[x][y] = ma[y][x] = 1; } ans[++id] = 1; vis[1] = 1; dfs(1); for(int i = 1;i <= n; i++) printf("%d ", ans[i]); return ; } } namespace task2{ /*taks2: 枚举删边*/ struct node1{ int x, y; } a[N]; vector <int> G[N]; /*用来排序比较方便*/ struct node{ int v, next; } t[N << 1]; int f[N]; int bian = 0; inline void add(int u, int v){ t[++bian] = (node){v, f[u]}, f[u] = bian; return ; } int dfn[N] , low[N], cnt = 0, cac = 0; int stac[N], top = 0, scc[N]; bool in[N]; void tarjan(int now){ dfn[now] = low[now] = ++cac; stac[++top] = now; in[now] = 1; for(int i = f[now]; i; i = t[i].next){ int v = t[i].v; if(!dfn[v]){ tarjan(v); low[now] = min(low[now], low[v]); } else if(in[v]) low[now] = min(low[now], dfn[v]); } if(low[now] == dfn[now]){ int cur; cnt++; do{ cur = stac[top--]; scc[cur] = cnt; in[cur] = 0; } while(cur != now) ; } return ; } int du, dv; bool vis[N]; int sum[N]; inline bool cmp(int a, int b){ return a > b; } bool check(){ /*检查字典序大小*/ for(register int i = 1;i <= n; i++) if(cur[i] != ans[i]) return ans[i] > cur[i]; return 0; } inline bool check_edge(int u, int v){ /*保证不是删边*/ if((u == du && v == dv) || (u == dv && v == du)) return 0; else return 1; } void dfs(int now){ cur[++id] = now; vis[now] = 1; for(int i = f[now]; i; i = t[i].next){ int v = t[i].v; if(!vis[v] && check_edge(now, v)) dfs(v); } return ; } void main(){ for(int i = 1;i <= m; i++){ int x = read(), y = read(); a[i].x = x, a[i].y = y; /*存边，用来*/ G[x].push_back(y), G[y].push_back(x); } for(register int i = 1;i <= n; i++) sort(G[i].begin(), G[i].end(), cmp); for(register int i = 1;i <= n; i++){ for(int j = 0;j < G[i].size(); j++) add(i, G[i][j]); } tarjan(1); /*预先找环*/ memset(ans, 127, sizeof(ans)); for(int i = 1;i <= m; i++){ du = a[i].x, dv = a[i].y; if(scc[du] != scc[dv]) continue; /*不在一个环中，则删除后必不成立（图要连通）*/ memset(vis, 0, sizeof(vis));/*记得清零*/ id = 0; vis[1] = 1; dfs(1); if(check()) memcpy(ans, cur, sizeof(cur)); } for(register int i = 1;i <= n; i++) printf("%d ", ans[i]); return ; } } int main(){ // freopen("P5022_19.in", "r", stdin); n = read(), m = read(); if(m == n - 1) task1::main(); /*分情况来*/ else task2::main(); return 0; }
总得来说，就是一道细节（码量略大） 和 优化 （卡常）题。