1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	n       int
	graph   [][]int
	visited []bool
	N, M, V int
	r       *bufio.Reader
	w       *bufio.Writer
)

func main() {
	r = bufio.NewReader(os.Stdin)
	w = bufio.NewWriter(os.Stdout)

	fmt.Fscanln(r, &N, &M, &V)

	graph = make([][]int, N+1)
	visited = make([]bool, N+1)

	for i := range graph {
		graph[i] = make([]int, N+1)
	}

	for i := 0; i < M; i++ {
		var x, y int
		fmt.Fscan(r, &x, &y)
		graph[x][y] = 1
		graph[y][x] = 1
	}

	dfs(V)
	w.Flush()
	resetVisited()
	fmt.Println()

	bfs(V)
}

func dfs(V int) {
	visited[V] = true
	fmt.Fprint(w, V, " ")
	for i := 0; i < len(graph[V]); i++ {
		if graph[V][i] == 1 && !visited[i] {
			dfs(i)
		}
	}
}

func bfs(V int) {
	visited[V] = true
	q := []int{V}

	for len(q) != 0 {
		front := q[0]
		fmt.Print(front, " ")
		q = q[1:]
		for i := 0; i <= N; i++ {
			if graph[front][i] == 1 && !visited[i] {
				visited[i] = true
				q = append(q, i)
			}
		}
	}
}

func resetVisited() {
	for i := 0; i < len(visited); i++ {
		visited[i] = false
	}
}