[11724] 연결 요소의 개수

문제

11724번: 연결 요소의 개수

 

 

내 코드(C / C++)

Ver.1(C++)

// [11724] 연결 요소의 개수
// https://www.acmicpc.net/problem/1260

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1001
using namespace std;

bool visit[MAX];
vector<int>list[MAX];
void dfs(int start);
int cc = 0; // the number of connected components

int main(void)
{
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int u, v; // 간선의 양 끝 점
		cin >> u >> v;
		list[u].push_back(v);
		list[v].push_back(u);
	}
    
    // 노드는 1부터 시작
	for (int i = 1; i <= N; i++) {
    	if (!visit[i]) {
			dfs(i);
			cc++; // dfs가 새롭게 호출된 횟수 = 연결 요소의 개수
		}
    }
	cout << cc;
}

void dfs(int start)
{
	visit[start] = true; // 방문
	for (int i = 0; i < list[start].size(); i++) {
		int next = list[start][i];
		if (visit[next] == false)
			dfs(next);
	}
}

 

Ver.2(C)

// [11724] 연결 요소의 개수
// dfs가 새롭게 호출된 횟수 = 연결 요소의 개수

#include <stdio.h>
#define MAX 1001

int n, m; // 정점의 개수, 간선의 개수
int visit[MAX];
int matrix[MAX][MAX];

void dfs(int v);

int main(void)
{
	int u, v; // 간선의 양 끝점
	int count = 0; // 새로 dfs가 호출된 횟수
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &u, &v);
		matrix[u][v] = 1;
		matrix[v][u] = 1;
	}
    
    // 노드는 1부터 시작
	for(int i=1;i<=n;i++) {
    	if (!visit[i]) {
			dfs(i);
			count++; // dfs가 새롭게 호출된 횟수 = 연결 요소의 개수
		}
    }
	printf("%d", count);
	return 0;
}

void dfs(int v)
{
	for (int i = 1; i <= n; i++) {
    	if (matrix[v][i] == 1 && !visit[i]) {
			visit[i] = 1; // 방문함
			dfs(i);
		}
    }
}