SWEA - 7465 창용 마을 무리의 개수

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU

SW Expert Academy

창용마을에 살고 있는 사람들의 무리 개수를 구하는 문제였다.

 

문제 풀이

창용마을에 사는 사람들을 입력받아 그래프 벡터에 저장하고, 1부터 N까지의 사람들이 방문되지 않았다면 dfs를 돌려 그 사람과 연결된 사람들을 방문처리 해주며 풀었다. 이때 dfs를 돌린 횟수가 무리의 개수와 동일하다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int visit[102] = {0};

void dfs(int n, vector<vector<int>> g){
    visit[n] = 1;
    
    for(int i=0;i<g[n].size();i++){
        int nextNode = g[n][i];
     	if(visit[nextNode] == 0){
         	dfs(nextNode, g);   
        }
    }
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
    int N,M;
    int a,b;
    int answer;
    
	cin>>T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        scanf("%d %d",&N,&M);
        vector<vector<int>> g(N+1);
        fill(visit, visit+101,0);
        answer = 0;
        
        for(int i=0;i<M;i++){
            scanf("%d %d",&a,&b);
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        for(int i=1;i<=N;i++){
            if(visit[i] == 0){
             	dfs(i,g);
                answer++;
            }
        }
        
        printf("#%d %d\n",test_case, answer);
	}
	return 0;
}