NOIP 2018 旅行

题目

落谷-》5022

题解

对于n > m 当成一个树遍历， 对于n = m暴力删边，然后dfs

CODE

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>    
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define R register
using namespace std;
typedef long long ull;
const int maxn = 5e3 + 100;

inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    return s * w;
}

inline void write(int x)
{
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

vector <int> vec[maxn];
int ans[maxn], edge[maxn][2], t[maxn], vis[maxn];
int n, m, da, db, tsize = 0;

inline void dfs(int x) {
    t[++tsize] = x; vis[x] = 1;
    int l = vec[x].size();
    for (R int i = 0; i < l; ++i) {
        int y = vec[x][i];
        if (!vis[y] && !((x == da && y == db) || (x == db && y == da))) dfs(y);
    }
    return ;
}

inline void check() {
    if (tsize != n) return ;
    for (R int i = 1; i <= n; ++i) {
        if (t[i] != ans[i]) {
            if (t[i] > ans[i]) return ;
            break;
        }
    }
    for (R int i = 1; i <= n; ++i) {
        ans[i] = t[i];
    }
    return ;
}

int main() {
//	freopen("Ain.txt","r",stdin);
    memset(ans, 0x3f, sizeof(ans));
    n = read(), m = read();
    for (R int i = 1; i <= m; ++i) {
        int a = read(), b = read();
        vec[a].push_back(b);
        vec[b].push_back(a);
        edge[i][0] = a;
        edge[i][1] = b;
    }
    for (R int i  = 1; i <= n; ++i) sort(vec[i].begin(), vec[i].end());
    if (n > m) {
        da = -1, db = -1;
        dfs(1);
        check();
    }
    else {
        for (R int i = 1; i <= m; ++i) {
            tsize = 0;
            da = edge[i][0];
            db = edge[i][1];
            memset(vis, 0, sizeof(vis));
            dfs(1);
            check();
        }
    }
    for (R int i = 1; i <= n; ++i) write(ans[i]), putchar(' ');
    return 0;
}