# Untitled

unknown
plain_text
10 months ago
2.7 kB
4
Indexable
Never
```import java.util.Scanner;

public class Solution {

static int N, M, min;
static int[][] a;
static boolean[] visited, total, visited2;

static void solve(int u) {
int count = 0;
for (int i = 1; i <= N; i++) {
if (visited[i]) {
count++;
}
}
if (count >= min) {
return;
}
if (u == 2) {
for (int i = 1; i <= N; i++) {
total[i] = visited[i];
visited2[i] = false;
}
visited[2] = true;
solve2(u);
return;
}
for (int v = 1; v <= N; v++) {
if (a[u][v] == 1 && !visited[v]) {
visited[v] = true;
solve(v);
visited[v] = false;
}
}
}

static void solve2(int u) {
int count = 0;
for (int i = 1; i <= N; i++) {
if (total[i] || visited2[i]) {
count++;
}
}
if (count >= min) {
return;
}
if (u == 1) {
count = 0;
for (int i = 1; i <= N; i++) {
if (total[i] || visited2[i]) {
count++;
}
}
min = count < min ? count : min;
}
for (int v = 1; v <= N; v++) {
if (a[u][v] == 1 && !visited2[v]) {
visited2[v] = true;
solve2(v);
visited2[v] = false;
}
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tcs = sc.nextInt();
for (int tc = 1; tc <= tcs; tc++) {
N = sc.nextInt();
M = sc.nextInt();
a = new int[N + 1][N + 1];
visited = new boolean[N + 1];
visited2 = new boolean[N + 1];
total = new boolean[N + 1];
visited[1] = true;
visited2[2] = true;
for (int i = 0; i < M; i++) {
a[sc.nextInt()][sc.nextInt()] = 1;
}
min = 10000000;
solve(1);
System.out.println(min);
}
}
}

4
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3
9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1
12 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1
16 144
3 9
10 3
1 14
6 10
12 2
10 9
11 6
12 11
16 11
3 1
14 12
5 10
15 7
1 15
9 16
6 12
8 16
14 8
13 4
2 8
5 11
16 15
10 16
16 3
8 5
12 6
11 12
4 3
11 10
14 3
9 12
10 5
15 11
13 3
2 5
7 11
4 12
6 4
14 13
8 9
3 2
4 6
4 14
15 2
16 7
13 10
4 8
13 9
3 14
14 9
8 1
4 1
10 11
2 16
1 9
7 13
7 6
9 3
14 11
1 11
12 7
5 15
8 15
4 5
11 4
13 1
2 6
4 10
9 1
4 9
14 5
3 15
14 2
15 1
11 7
15 12
5 14
2 7
16 6
8 6
12 10
6 5
9 6
13 6
6 1
1 7
14 15
10 8
2 13
3 8
6 14
2 10
16 14
15 6
9 5
6 9
11 3
8 12
5 4
1 8
6 7
1 5
15 16
2 14
3 12
7 1
13 5
3 16
7 8
7 10
14 7
7 16
9 11
9 10
5 1
1 16
10 4
6 16
10 7
7 3
11 1
2 12
12 13
13 15
15 10
4 15
5 8
16 4
8 13
7 12
6 8
7 2
4 13
10 14
15 13
15 3
11 15
6 15
16 10
1 6
7 5
8 4
10 6
1 13```