[M1721] 창용 마을 무리의 개수

• ※ 문제 및 풀이에 대해 사외 온라인/오프라인에 게시/공유 하는 것은 금지되어 있습니다.  
     SW Expert 아카데미의 문제는 삼성전자 직원에게만 오픈 되어 있습니다.

  
  

   [제한 사항]

  
  

  시간	10개 테스트케이스를 합쳐서 C/C++의 경우 1초 / Java의 경우 2초
  메모리	힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

  
  

  
  

  창용 마을에는 N명의 사람이 살고 있다.

  
  

  사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다.

  
  

  두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다.

  
  

  두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다.

  
  

  창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라.

  
  

  
  

  [입력]

  
  

  첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

  
  

  각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는

  
  

  두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다.

  
  

  이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다.

  
  

  같은 관계는 반복해서 주어지지 않는다.

  
  

  
  

  [출력]

  
  

  각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

  
  

  무리의 개수를 출력한다.

  
  

  
  

  입력 예제
  2 6 5 1 2 2 5 5 1 3 4 4 6 6 8 1 2 2 5 5 1 3 4 4 6 5 4 2 4 2 3	// 테스트 케이스 개수 // 첫 번째 테스트 케이스, N = 6, M = 5           // 두 번째 테스트 케이스, N = 6, M = 8

  
  

  출력 예제
  #1 2 #2 1	// 첫 번째 테스트 케이스 결과 // 두 번째 테스트 케이스 결과

#include <stdio.h> int fa[2005],sz[2005]; int get(int x) {     if(fa[x]==x)return x;     return fa[x] = get(fa[x]); } void unite(int x, int y) {     x = get(x);     y = get(y);     if(x==y)return;     if(sz[x] < sz[y])     {         int tmp = x;         x = y;         y = tmp;     }     fa[y] = x;     sz[x] += sz[y]; } int main(void) {     int test_case;     int T;       setbuf(stdout, NULL);     scanf("%d", &T);       for (test_case = 1; test_case <= T; ++test_case)     {         int n,m,i,x,y,ans=0;         scanf("%d%d",&n,&m);         for(i=1;i<=n;i++)         {             fa[i] = i;             sz[i] = 1;         }         for(i=1;i<=m;i++)         {             scanf("%d%d",&x,&y);             unite(x,y);         }         for(i=1;i<=n;i++)             if(fa[i]==i)ans++;         printf("#%d %d\n",test_case,ans);     }     return 0; }

•