BOJ / 11724번 / 연결 요소의 개수 [Go][Python3]

👩🏻‍💻 문제

11724번: 연결 요소의 개수

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/11724
package main

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

var (
	graph   [][]int
	visited []bool
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m int
	fmt.Fscanln(reader, &n, &m)

	graph = make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		graph[i] = make([]int, n+1)
	}
	visited = make([]bool, n+1)

	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscanln(reader, &u, &v)
		graph[u][v] = 1
		graph[v][u] = 1
	}

	var numOfConnected int
	for i := 0; i < n+1; i++ {
		if !visited[i] {
			numOfConnected++
			dfs(i)
		}
	}
	fmt.Fprintln(writer, numOfConnected-1)
}

func dfs(start int) {
	visited[start] = true
	for i := 0; i < len(graph); i++ {
		if !visited[i] && graph[start][i] == 1 {
			dfs(i)
		}
	}
}

🎨 Python3

# https://www.acmicpc.net/problem/11724
import sys

sys.setrecursionlimit(10000)

graph = []
visited = []

def dfs(start):
    global graph
    global visited
    visited[start] = True
    for i in range(len(graph)):
        if not visited[i] and graph[start][i] == 1:
            dfs(i)

if __name__ == "__main__":
    n, m = list(map(int, sys.stdin.readline().split()))
    graph = [[0 for i in range(n+1)] for j in range(n+1)]
    visited = [False for i in range(n+1)]

    for i in range(m):
        u, v = list(map(int, sys.stdin.readline().split()))
        graph[u][v] = 1
        graph[v][u] = 1

    num_of_connected = 0
    for i in range(n+1):
        if not visited[i]:
            num_of_connected += 1
            dfs(i)
    print(num_of_connected-1)