백준11724(연결 요소의 개수)

jh Seo·2022년 11월 11일

DFS 백준 한번에 푼 문제

백준

목록 보기

73/180

개요

백준 11724번: 연결 요소의 개수

입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.

접근 방법

그래프를 새로 클래스로 구현하여 짰다.
방문 여부를 저장하는 visit벡터와 간선정보를 저장하는 adj벡터, 노드의 갯수를 선언하였고,
간선 연결해주는 addEdge(int u,int v),
노드에 연결되어있는 다른 노드들을 정렬해주는 sortAdj(),
dfs를 이용하여 컴퍼넌트 갯수를 반환하는 returnComponents()
등의 함수등을 구현하였다.

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Graph {
private:
	int Nodes;
	vector<vector<int>> adj;
	vector<int> visited;
public:
	//생성자
	Graph(int N) :Nodes(N) {
		adj.resize(N+1);
		visited.resize(N+1);
	}

	//양방향으로 짰으므로 u와 v노드 서로 연결
	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	//각 노드와 연결된 노드들을 오름차순으로 정렬
	void sortAdj(){
		for (int i = 1; i <= Nodes; i++) {
			sort(adj[i].begin(), adj[i].end());
		}
	}
	/// <summary>
	/// 각 정점마다 dfs 실행
	/// </summary>
	/// <returns>그래프 내의 컴퍼넌트 갯수</returns>
	int returnComponents(){
		int components = 0;
		for (int i = 1; i <= Nodes; i++) {
			if (!visited[i]) {
				components++;
				dfs(i);
			}
		}
		return components;
	}
	/// <summary>
	/// 매개변수로 들어온 Node정점에서 dfs로 연결요소들 탐색
	/// </summary>
	/// <param name="Node"></param>
	void dfs(int Node) {
		if (visited[Node]) return;
		visited[Node] = true;
		for (int k : adj[Node]) {
			if (!visited[k]) {
				dfs(k);
			}
		}
	}
};

void input() {
	int inputNodes = 0, inputEdges = 0,edge1=0,edge2=0;
	cin >> inputNodes >> inputEdges;
	//그래프 선언
	Graph g(inputNodes);
	g.sortAdj();
	for (int i = 0; i < inputEdges; i++) {
		cin >> edge1 >> edge2;
		g.addEdge(edge1, edge2);
	}
	cout << g.returnComponents();
}

int main() {
	input();
}