参考第一篇题解,样例没过!求调!
查看原帖
参考第一篇题解,样例没过!求调!
519573
Daniel_yao楼主2022/7/25 15:15
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 100005;

int n, m, nx[N], cnt[2], rd[N], cd[N], s, tot, stk[N];

bool flag = 1;

vector <int> e[N];

void dfs(int x) {
	for (int i = nx[x]; i < e[x].size(); i = nx[x]) {
		nx[x] = i + 1;
		dfs(e[x][i]);
	}
	stk[++tot] = x;
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		rd[v]++, cd[u]++;
	}
	for(int i = 1; i <= n; i++) {
		sort(e[i].begin(), e[i].end());
	}
	for (int i = 1; i <= n; i++) {
		if(rd[i] != cd[i]) flag = 0;
		if(cd[i] - rd[i] == 1) cnt[1]++, s = i;
		if(rd[i] - cd[i] == 1) cnt[0]++; 
	}
//	nx[s] = 1;
	if(!flag && !(cnt[0] == cnt[1] && cnt[0] == 1)) return printf("No\n"),0;
	dfs(s);
	while(tot) {
		cout << stk[tot--] << ' ';
	}
	return 0;
}
2022/7/25 15:15
加载中...