[C] 11724: 연결 요소의 개수

일단 이 문제도 결국  그래프 탐색 문제이다.

최단 거리와 관계가 없고 그냥 그래프가 서로 이어져 있냐만 확인하면 되므로

Depth-first(깊이 우선탐색)을 이용하여 인접행렬을 통해 문제를 풀었다.

 

여기서 유일하게 주의해야 할점은 노드가 하나라도 독립적인 연결 요소가 된다는 것이다.

그렇기 때문에 인접행렬에서 자기자신에게 가는 간선도 추가해줘야 간단히 풀 수 있다.

 

#include <stdio.h>

int graph[1001][1001];
int visit[1001][1001];

void dfs(int n, int line, int x, int y)
{
  for(int i=1;i<=n;i++)
    {
      if(graph[x][i]==1 && visit[x][i]==0)
      {
        visit[x][i]=1;
        dfs(n,line,i,x);
        
      }
    }
}

int main(void)
  {
    int node,line,cnt=0;
    scanf("%d %d",&node,&line);

    for(int i=1;i<=node;i++)
      {
        graph[i][i]=1;
      }

    for(int i=1;i<=line;i++)
      {
        int a,b;
        scanf("%d %d",&a,&b);
        graph[a][b]=1;
        graph[b][a]=1;

      }
    for(int j=1;j<=node;j++)
      {
        for(int i=1;i<=node;i++)
          {
            if(visit[j][i]==0 && graph[j][i]==1)
            {
              visit[j][i]=1;
              //if()
              dfs(node,line,i,j);
              cnt++;
            }
          }
      }
    

    printf("%d",cnt);
    
  }