개요

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

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

• 출력
  첫째 줄에 연결 요소의 개수를 출력한다.

접근 방법

1. 그래프를 새로 클래스로 구현하여 짰다.
   방문 여부를 저장하는 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();
}

문풀후생

그래프에 연결된 정점들을 넣어줘서 컴퍼넌트를 반환하면 끝난다.

레퍼런스

그래프 공부 참고한 블로그