그래프

용어 정의

그래프 : 꼭짓점과 변으로 이루어진 자료구조

트리 : 연결이면서 사이클이 없는 그래프

이진 힙 : 이진트리를 배열로 구연한 것 (priority_queue)

Union-Find : 그룹 분할을 관리함

구현 예시

비가중 그래프

using Graph = vector<vector<int>>
 
int main() {
	int N, M;
	cin << N << M;
	Graph G(N);
	for(int i = 0; i < M; i++){
		int a, b;
		cin << a << b;
		g[a].push_back(b);
		// 만약 무향 그래프라면
		g[b].push_back(a);
	}
}

가중 그래프

struct Edge{
	int to, weight;
	Edge(int t, int w) : to(t), weight(w) {}
};
 
using Graph = vector<vector<Edge>>;
 
int main() {
	int N, M;
	cin << N << M;
	Graph g(N);
	for(int i = 0; i < M; i++){
		int a, b, w;
		cin << a << b << w;
		g[a].push_back(Edge(b, w));
	}
}

참고자료

문제 해결력을 높이는 알고리즘과 자료 구조