[11724] 연결 요소의 개수, C/C++

한줄 후기 : 쩝

 

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

#include <stdio.h>
#define MAX 1002
int graph[MAX][MAX] = {0,};
int visit[MAX]={0};
int vertex, edge;
int DFS(int v);
int main(){
	int cnt=0;
	int i, a,b;
	scanf("%d %d\n", &vertex, &edge);
	for(i=0; i<edge; i++){
		scanf("%d %d", &a, &b);
		graph[a][b]= 1;
		graph[b][a]= 1;
	}
	for(i=1; i<=vertex; i++){
		if(!visit[i]){
			DFS(i);
			cnt++;
		}
	}
	printf("%d", cnt);
	return 0;
}
int DFS(int v){
	int i;
	visit[v] = 1;
	for(i=1; i<=vertex; i++){
		if(graph[v][i]){
			if(!visit[i]) 	DFS(i);
		}
	}
	return;
}

c로 푼 코드, 인접행렬 만들고 DFS 사용

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool visit[1002]={false}; 
vector<int> met[1002];
int dfs(int start);
int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i<m; i++){
		int u, v;
		cin >> u >> v;
		met[u].push_back(v);
		met[v]. push_back(u);
	}
	int cnt = 0;
	for(int i=1; i<=n; i++){
		if(visit[i] == false){
			dfs(i);
			cnt++;
		}
	}
	cout << cnt;
}
int dfs(int start){
	visit[start] = true;
	for(int i=0; i < met[start].size(); i++ ){
		int next = met[start][i];
		if(visit[next]==false)	dfs(next);
	}
}

 

c++로 푼 DFS 이용 코드 벡터를 이용해 연결된 정점을 넣어준다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool visit[1002]={false}; 
vector<int> met[1002];
int bfs(int start);
int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i<m; i++){
		int u, v;
		cin >> u >> v;
		met[u].push_back(v);
		met[v]. push_back(u);
	}
	int cnt = 0;
	for(int i=1; i<=n; i++){
		if(visit[i] == false){
			bfs(i);
			cnt++;
		}
	}
	cout << cnt;
}
int bfs(int start){
	queue<int> q;
	visit[start] = true;
	q.push(start);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i=0; i<met[now].size(); i++){
			int next = met[now][i];
			if(visit[next]==false) {
				visit[next] = true;
				q.push(next);
			}
		} 
	}
}

c++로 푼 BFS 이용 코드

벡터와 큐를 사용