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

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

11724번: 연결 요소의 개수

연결 리스트 연습하려고 푼 문제인데 매트릭스로 만들어도 무방할듯!

 

#include <iostream>
#include <vector>

using namespace std;

class Graph {
public:
	int N;
	vector<vector<int>> adj;
	vector<bool> visited;

	Graph(int n) : N(n) {
		adj.resize(N);
		visited.resize(N);
	}

	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int dfs() {
		int components = 0;
		fill(visited.begin(), visited.end(), false);
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				dfs(i);
				components++;
			}
		}
		return components;
	}

private:
	void dfs(int curr) {
		visited[curr] = true;
		for (int next : adj[curr])
			if (!visited[next]) dfs(next);
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	Graph graph(n);

	while (m--) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		graph.addEdge(u, v);
	}

	cout << graph.dfs();
}