提交记录 6952


用户 题目 状态 得分 用时 内存 语言 代码长度
wys noip18d. 【NOIP2018】旅行 Accepted 100 2.004 ms 508 KB C++ 1.71 KB
提交时间 评测时间
2018-11-20 14:57:09 2020-08-01 00:54:51
// linear.cpp 18-10-28 wys

#include <stdio.h>
#include <algorithm>

const int MAXN = 300005;

int n, m;

struct edge {
	int u, v, id;
};

bool operator < (const edge &a, const edge &b) {
	return a.u < b.u || (a.u == b.u && a.v < b.v);
}

edge edges[MAXN * 2];
edge *first[MAXN];

int stack[MAXN];
int stack_eid[MAXN];
bool instack[MAXN];
int top;
bool found;

bool is_on_cycle[MAXN];

void dfs(int u, int last) {
	stack[++top] = u;
	instack[u] = true;
	for (edge *e = first[u]; e->u == u; e++) {
		int v = e->v;
		if (v == last) continue;
		if (instack[v]) {
			found = true;
			is_on_cycle[e->id] = true;
			while (stack[top] != v) {
				is_on_cycle[stack_eid[top - 1]] = true;
				--top;
			}
			return;
		}
		stack_eid[top] = e->id;
		dfs(v, u);
		if (found) return;
	}
	instack[u] = false;
	--top;
}

int ans_idx;

bool visit[MAXN];
bool del;

void dfs(int u) {
	printf("%d%c", u, " \n"[++ans_idx == n]);
	visit[u] = true;
	++top;
	bool done = false;
	for (edge *e = first[u]; e->u == u; e++) {
		int v = e->v;
		if (visit[v]) continue;
		edge *e1 = e + 1;
		while (e1->u == u && visit[e1->v]) ++e1;
		if (e1->u == u) {
			stack[top] = e1->v;
		} else {
			--top;
			done = true;
		}
		if (!del && is_on_cycle[e->id] && v > stack[top]) {
			del = true;
		} else {
			dfs(v);
		}
	}
	if (!done) --top;
}

int main() {
	scanf("%d%d", &n, &m);
	if (n == 1) {
		return puts("1"), 0;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		edges[i * 2] = (edge){u, v, i};
		edges[i * 2 + 1] = (edge){v, u, i};
	}
	std::sort(edges, edges + 2 * m);
	first[1] = edges;
	for (int i = 1; i < 2 * m; i++) {
		if (edges[i].u != edges[i - 1].u) {
			first[edges[i].u] = edges + i;
		}
	}
	dfs(1, 0);
	top = 0;
	stack[0] = n + 1;
	dfs(1);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #114.94 us44 KBAcceptedScore: 4

Testcase #217.78 us44 KBAcceptedScore: 4

Testcase #319.15 us44 KBAcceptedScore: 4

Testcase #448.35 us64 KBAcceptedScore: 4

Testcase #546.31 us56 KBAcceptedScore: 4

Testcase #6364.44 us132 KBAcceptedScore: 4

Testcase #7364.45 us132 KBAcceptedScore: 4

Testcase #8366.7 us136 KBAcceptedScore: 4

Testcase #9379.76 us116 KBAcceptedScore: 4

Testcase #10381.57 us112 KBAcceptedScore: 4

Testcase #112.004 ms400 KBAcceptedScore: 4

Testcase #121.992 ms456 KBAcceptedScore: 4

Testcase #131.986 ms472 KBAcceptedScore: 4

Testcase #141.988 ms396 KBAcceptedScore: 4

Testcase #151.98 ms508 KBAcceptedScore: 4

Testcase #1615.23 us44 KBAcceptedScore: 4

Testcase #1715.17 us44 KBAcceptedScore: 4

Testcase #1846.01 us64 KBAcceptedScore: 4

Testcase #1946.71 us64 KBAcceptedScore: 4

Testcase #20363.53 us144 KBAcceptedScore: 4

Testcase #21363.56 us144 KBAcceptedScore: 4

Testcase #22363.06 us144 KBAcceptedScore: 4

Testcase #231.967 ms488 KBAcceptedScore: 4

Testcase #241.977 ms472 KBAcceptedScore: 4

Testcase #251.985 ms452 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 12:59:39 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用