728x90
반응형
https://www.acmicpc.net/problem/24444
24444번: 알고리즘 수업 - 너비 우선 탐색 1
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> e(100001);
int visited[100001];
int cnt = 1;
void bfs(int w){
visited[w] = cnt++;
queue<int> q;
q.push(w);
while(!q.empty()){
int node = q.front();
q.pop();
for(int i = 0; i < e[node].size(); i++){
if(!visited[e[node][i]]){
visited[e[node][i]] = cnt++;
q.push(e[node][i]);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, r, u, v;
cin >> n >> m >> r;
for(int i = 0; i < m; i++){
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i = 1; i <= n; i++){
sort(e[i].begin(), e[i].end());
}
bfs(r);
for(int i = 1; i <= n; i++){
cout << visited[i] << '\n';
}
return 0;
}
https://www.acmicpc.net/problem/24445
24445번: 알고리즘 수업 - 너비 우선 탐색 2
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양
www.acmicpc.net
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> e(100001);
int visited[100001];
int cnt = 1;
void bfs(int w){
visited[w] = cnt++;
queue<int> q;
q.push(w);
while(!q.empty()){
int node = q.front();
q.pop();
for(int i = 0; i < e[node].size(); i++){
if(!visited[e[node][i]]){
visited[e[node][i]] = cnt++;
q.push(e[node][i]);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, r, u, v;
cin >> n >> m >> r;
for(int i = 0; i < m; i++){
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i = 1; i <= n; i++){
sort(e[i].begin(), e[i].end(), greater<>());
}
bfs(r);
for(int i = 1; i <= n; i++){
cout << visited[i] << '\n';
}
return 0;
}728x90
반응형
'Algorithm > BAEKJOON' 카테고리의 다른 글
| [BOJ] 1543번 문서 검색 (C++) (0) | 2022.02.16 |
|---|---|
| [BOJ] 1485번 정사각형 (C++) (0) | 2022.02.15 |
| [BOJ] 24479번, 24480번 알고리즘 수업 - 깊이 우선 탐색 1, 2 (C++) (0) | 2022.02.15 |
| [BOJ] 15989번 1, 2, 3 더하기 4 (C++) (0) | 2022.02.14 |
| [BOJ] 16165번 걸그룹 마스터 준석이 (C++) (0) | 2022.02.14 |
