Submission #68645842

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return a < b ? -1 : a > b;
}
int N, M, X, Y;
int ec[1024];
int es[1024][1024];
int tc;
int visited[1024];
int num;
int path[1024];
int dfs(int node) {
  int i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

int N, M, X, Y;
int ec[1024];
int es[1024][1024];

int tc;
int visited[1024];

int num;
int path[1024];

int dfs(int node) {
	int i;
	int found = 0;
	if (visited[node] == tc) return 0;
	visited[node] = tc;
	path[num++] = node;
	if (node == Y) {
		for (i = 0; i < num; i++) {
			printf(" %d" + !i, path[i]);
		}
		putchar('\n');
		found = 1;
	} else {
		for (i = 0; !found && i < ec[node]; i++) {
			found = dfs(es[node][i]);
		}
	}
	num--;
	/* 通ってたどり着けなかったノードは、再探索しない */
	/* visited[node] = 0; */
	return found;
}

int main(void) {
	int T;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 1; tc <= T; tc++) {
		int i;
		if (scanf("%d%d%d%d", &N, &M, &X, &Y) != 4) return 1;
		memset(ec, 0, sizeof(ec));
		for (i = 0; i < M; i++) {
			int U, V;
			if (scanf("%d%d", &U, &V) != 2) return 1;
			es[U][ec[U]++] = V;
			es[V][ec[V]++] = U;
		}
		for (i = 1; i <= N; i++) {
			if (ec[i] > 0) qsort(es[i], ec[i], sizeof(*es[i]), cmp);
		}
		num = 0;
		dfs(X);
	}
	return 0;
}

/*

辞書順 → とにかく前に強いやつを取ってしまうのが吉

たどり着けるならよい (予想)
だが……たどり着けないならどうかな？

```python:gen.py
N = 300

print(1)
print("%d %d %d %d" % (N, (N - 1) * (N - 2) // 2 + 1, N - 1, N))
for i in range(1, N - 1):
    for j in range(i + 1, N):
        print("%d %d" % (i, j))
print("%d %d" % (N - 1, N))
```

*/

Submission Info

Judge Result