BOJ 24445 알고리즘 수업 - 너비 우선 탐색 2

1 개요

BOJ 24445 알고리즘 수업 - 너비 우선 탐색 2

• 백준 온라인 저지 24445번 문제
• BOJ 31단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N, M, R;
vector<int> G[100001];
int visited[100001];
int cnt = 0;

void bfs() {
    queue<int> q;
    q.push(R);
	cnt++;
	visited[R] = cnt;
	int u, v;
	while(!q.empty()) {
	    u = q.front();
	    q.pop();
	    for(int i=0; i<G[u].size(); i++) {
	        v = G[u][i];
	        if(!visited[v]) {
	            cnt++;
	            visited[v] = cnt;
	            q.push(v);
	        }
	    }
	}
}

int main() {
	scanf("%d %d %d", &N, &M, &R);
	int a, b;
	for(int i=1; i<=M; i++) {
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i=1; i<=N; i++) {
		sort(G[i].begin(), G[i].end(), greater<int>());
	}
	bfs();
	for(int i=1; i<=N; i++) {
		printf("%d\n", visited[i]);
	}
}