84分 求助大佬
查看原帖
84分 求助大佬
251802
Liutian1112楼主2020/11/10 15:26
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
const ll mod = 1e9 + 7;

vector<int> G[maxn];
int dfn[maxn], low[maxn], idx;
int color[maxn], cnt;
int stk[maxn], top;

// 找环
void tarjan(int u, int fa)
{
    sort(G[u].begin(), G[u].end());
    dfn[u] = low[u] = ++idx;
    stk[top++] = u;
    for(const int& v : G[u]) {
        if(!dfn[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        } else if(v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        int now;
        cnt++;
        do{
            now = stk[--top];
            color[now] = cnt;
        }while(now != u);
    }
}


// 搜索
bool flag = true; // 只能回溯一次
bool vis[maxn];
void dfs(int u, int ma)
{
    cout << u << " ";
    vis[u] = true;
    for(int i = 0; i < G[u].size()-1; i++) {
        int v = G[u][i];
        if(vis[v]) continue;
        dfs(v, min(ma, G[u][i+1]));
    }
    int v = G[u].back();
    if(!vis[v]) {
        if(flag == true && v > ma && color[u] == color[v]) {
            flag = false;
        }
        else dfs(v, ma);
    }
}

int main()
{
    IOS();
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    tarjan(1, 0);
    dfs(1, INF);
    return 0;
}
2020/11/10 15:26
加载中...