(백준/c++) 24479 - 알고리즘 수업

(백준/c++) 24479 - 알고리즘 수업 - 깊이 우선 탐색 1📃 coding test/◽ 백준2022. 6. 2. 01:43@핑크코냥

Table of Contents

728x90

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양

www.acmicpc.net

인접리스트, DFS

* 주의

1. 문제에서 나온 알고리즘을 따라서 만들면 되지만 인접행렬로 코드를 짜게 되면 시간초과로 통과 할 수없었다. 인접 리스트로 코드를 작성해야 한다.

2. 무방향 그래프 이므로 양쪽으로 연결해줘야 한다.

	#include <iostream>
	#include <vector>
	#include <algorithm>
	//#include <memory.h> // memset
	using namespace std;
	#define MAXR 100'001
	// # V : 정점 집합, E : 간선 집합, R : 시작 정점
	// # 인접행렬과 인접리스트

	vector<int> Edge[MAXR];
	//int OrderOfVisit[MAXR]; <- 이걸로 하면 시간초과.
	vector<int> OrderOfVisit(MAXR, 0);
	int gOrderOfVisit;
	void DFS(int start);
	int main(void)
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, R;

	cin >> N >> M >> R;

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

	for (int i = 1; i <= N; ++i) {
	sort(Edge[i].begin(), Edge[i].end());
	}
	DFS(R);

	for (int i = 1; i <= N; ++i)
	{
	cout << OrderOfVisit[i] << "\n";
	}
	}

	void DFS(int start)
	{
	OrderOfVisit[start] = ++gOrderOfVisit;

	for (auto& aEdge : Edge[start]) {

	if (OrderOfVisit[aEdge])
	continue;

	DFS(aEdge);
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub

728x90