[백준] 11724 - 연결 요소의 개수

1. 문제

11724번: 연결 요소의 개수

2. 개요

방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

모든 정점들을 탐색하면서 방문하지 않은 정점이라면 방문처리하고 DFS를 실행하며 답을 1늘린다.

DFS중 만난 정점들은 방문처리한다.

모든 정점들을 탐색했다면 답을 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(100000)

N, M = map(int, sys.stdin.readline().split())

answer = 0
graph = [[] for i in range(N)]
visited = [False for i in range(N)]

for i in range(M):
    s, e = map(int, sys.stdin.readline().split())

    graph[s-1].append(e-1)
    graph[e-1].append(s-1)

def DFS(n):
    for next in graph[n]:
        if visited[next] == True:
            continue

        visited[next] = True
        DFS(next)

for i in range(N):
    if visited[i] == False:
        visited[i] = True
        answer += 1
        DFS(i)

print(answer)

3-3. C#

namespace boj_11724
{
    internal class Program
    {
        static List<List<int>> graph;
        static bool[] visited;

        static void Main(string[] args)
        {
            int answer = 0;

            string[] input = Console.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            graph = new List<List<int>>();
            for (int i = 0; i < N; i++)
                graph.Add(new List<int>());

            visited = new bool[N];

            for (int i = 0; i < M; i++)
            {
                string[] lines = Console.ReadLine().Split();
                int s = int.Parse(lines[0]);
                int e = int.Parse(lines[1]);

                graph[s - 1].Add(e - 1);
                graph[e - 1].Add(s - 1);
            }

            for (int i = 0; i < N; i++)
            {
                if (!visited[i])
                {
                    answer++;
                    visited[i] = true;
                    DFS(i);
                }
            }

            Console.WriteLine(answer);
        }

        static void DFS(int n)
        {
            foreach (int next in graph[n])
            {
                if (visited[next])
                    continue;

                visited[next] = true;
                DFS(next);
            }
        }
    }
}