[C++] vector를 이용하여 그래프를 인접리스트로 구현하기

vector<int> adj[10];

vector<int> *adj = new vector<int>[MAX_V];

// 개인적으로 좋아하는 표현
vector<vector<int>> adjList(N, vector<int>());

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

11724번: 연결 요소의 개수

이 문제로 그래프를 표현하면

int N, M;
cin >> N >> M;

vector<int>* adj = new vector<int>[N + 1];
for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

for (int i = 1; i <= N; i++) {
    cout << i << ": ";
    for (auto& node : adj[i]) {
        cout << node << " ";
    }
    cout << endl;
}

출력 결과

이 문제를 BFS로 푼 코드는 다음과 같다

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BOJ_Setup() {
	freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}


void bfs(vector<int> adj[], vector<int>& visit, int start, int cnt) {
	queue<int> q;
	q.push(start);
	visit[start] = cnt;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (auto& next : adj[cur]) {
			if (visit[next] == 0) {
				visit[next] = cnt;
				q.push(next);
			}
		}
	}
}

int main() {
	BOJ_Setup();

	int N, M;
	cin >> N >> M;

	vector<int>* adj = new vector<int>[N + 1];
	vector<int> visit(N + 1, 0);

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	int cnt = 1;
	for (int i = 1; i <= N; i++) {
		if (visit[i] == 0) {
			bfs(adj, visit, i, cnt);
			cnt += 1;
		}
	}

	cout << cnt - 1;

	return 0;
}

 

참고

https://www.geeksforgeeks.org/graph-implementation-using-stl-for-competitive-programming-set-1-dfs-of-unweighted-and-undirected/