백준 C# - 11724 +) 풀이

연결 요소(Connected Component)수 구하기

그래프에서 각 노드가 서로 연결된 갯수를 구하면 된다. 이는 한 노드를 잡고 DFS를 통해 그 노드에 연결된 모든 노드들을 방문한다. 이를 count를 증가시키면서 방문이 되지 않는 노드가 없을때까지 반복하면된다.

01 DFS

public static void dfs(int now)
{
    visited[now] = true;
    foreach (int next in graph[now])
    {
        if (visited[next])
            continue;
        dfs(next);
    }
}

---

02 그래프 입력받기

int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int n = input[0];
int m = input[1];
graph = new List<int>[n + 1];
visited = new bool[n + 1];
count = 0;
for (int i = 1; i <= n; i++)
{
    graph[i] = new List<int>();
}

for (int i = 0; i < m; i++)
{
    int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int u = edge[0];
    int v = edge[1];

    graph[u].Add(v);
    graph[v].Add(u);
}

---

03 방문하지 않는 노드가 없을때까지 DFS수행시키기

for (int i = 1; i<=n;i++)
{
    if(!visited[i])
    {
        count++;
        dfs(i);
    }
}

---

코드 전문

using System;
using System.Collections.Generic;

namespace baek2
{

   class Program 
   {
        static bool[] visited;
        static int count;
        static List<int>[] graph;
        public static void dfs(int now)
        {
            visited[now] = true;
            foreach(int next in graph[now])
            {
                if (visited[next])
                    continue;
                dfs(next);
            }
        }
        public static void Main()
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int n = input[0];
            int m = input[1];
            graph = new List<int>[n+1];
            visited = new bool[n + 1];
            count = 0;
            for (int i = 1; i<=n;i++)
            {
                graph[i] = new List<int>(); 
            }

            for(int i = 0; i<m; i++)
            {
                int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int u = edge[0];
                int v = edge[1];

                graph[u].Add(v);
                graph[v].Add(u);
            }

            for (int i = 1; i<=n;i++)
            {
                if(!visited[i])
                {
                    count++;
                    dfs(i);
                }
            }
            Console.Write(count);   
        }
   }
}