最后一个点 TLE 求调
查看原帖
最后一个点 TLE 求调
1211668
WMY_楼主2025/1/16 15:12
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define N 100005

int n, m;
vector<pair<int, int>> G[N];
int tot;
int in_deg[N], out_deg[N];

bool vis[N << 1];
vector<int> ans;

void dfs(int u) {
	for (auto x : G[u]) {
		if (!vis[x.second]) {
			vis[x.second] = 1;
			dfs(x.first);
		}
	}
	ans.push_back(u);
}

void solve() {
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		G[u].push_back(make_pair(v, ++tot));
		in_deg[v]++;
		out_deg[u]++;
	}
	int cnt1 = 0, cnt2 = 0, s;
	for (int i = 1; i <= n; i++) {
		if (in_deg[i] != out_deg[i]) {
			if (in_deg[i] == out_deg[i] - 1) cnt1++, s = i;
			else if (in_deg[i] == out_deg[i] + 1) cnt2++;
			else {
				puts("No");
				return;
			}
		}
	}
	if (!(cnt1 == cnt2 && (cnt1 == 0 || cnt1 == 1))) {
		puts("No");
		return;
	}
	for (int i = 1; i <= n; i++)
		sort(G[i].begin(), G[i].end());
	dfs(s);
	for (auto it = ans.rbegin(); it != ans.rend(); it++)
		cout << *it << " ";
	puts("");
}

int main() { solve(); }
2025/1/16 15:12
加载中...