안선생의 개발 블로그

C++ 24445 알고리즘 수업 - 너비 우선 탐색 2 본문

백준

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

안선생 2023. 2. 16. 14:49
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include<queue>
#include<algorithm>
using namespace std;
 
 
vector<int> g[200001] = {};
bool visit[200001] = {};
int n,m,k;
int result[200001] = {};
int abc = 1;
void bfs(int x)
{
    queue<int> a;
    a.push(x);
    visit[x] = 1;
    result[x] = abc++;
    while (!a.empty())
    {
        int x = a.front();
        a.pop();
       
        for (int i = 0; i < g[x].size(); i++)
        {
            int y = g[x][i];
            if (!visit[y])
            {
                a.push(y);
                visit[y] = 1;
                result[y] = abc++;
            }
 
        }
    }
 
}
int main(void)
{
    cin >> n >> m >> k;
   
    for (int i = 1; i <= m; i++)
    {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= m; i++)
    {
        sort(g[i].begin(), g[i].end(),greater<int>());
    }
    bfs(k);
    for (int i = 1; i <=n; i++)
    {
        cout << result[i] << "\n";
    }
    return 0;
}
 cs

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

 

'백준' 카테고리의 다른 글

C++ 1012 유기농 배추  (0) 2023.02.16
C++ 2178 미로 탐색  (0) 2023.02.16
C++ 24444 알고리즘 수업 - 너비 우선 탐색 1  (0) 2023.02.16
C++ 24480 알고리즘 수업 - 깊이 우선 탐색 2  (0) 2023.02.16
C++ 24479 알고리즘 수업 - 깊이 우선 탐색 1  (0) 2023.02.16
'백준' Related Articles more