안선생의 개발 블로그

C++ 11724 연결 요소의 개수 본문

백준

C++ 11724 연결 요소의 개수

안선생 2023. 2. 16. 12:11
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
59
60
61
62
63
#include <iostream>
#include <vector>
#include<queue>
#include<algorithm>
using namespace std;
 
vector<int> v;
int g[1001][1001] = {};
bool visit[1001] = {};
int n,m;
void dfs(int x)
{
    visit[x] = 1;
   // cout << x << " ";
    for (int i = 1; i <= n; i++)
    {
        if (!visit[i] && g[x][i])
        {
            dfs(i);
        }
    }
}
void bfs(int x)
{
    queue<int> a;
    a.push(x);
    visit[x] = 1;
    while (!a.empty())
    {
        int b = a.front();
        a.pop();
        for (int i= 1; i <= n; i++)
        {
            if (!visit[i] && g[b][i])
            {
                a.push(i);
                visit[i] = 1;
            }
        }
 
    }
}
int main(void)
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b; cin >> a >> b;
        g[a][b] = g[b][a]= 1;
    }
    int result = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!visit[i])
        {
            bfs(i);
            result++;
        }
    }
    cout << result;
    return 0;
}
 cs

https://www.acmicpc.net/problem/11724

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

 

계속 배열의 크기를 잘못 지정해서 틀린다..

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

C++ 24480 알고리즘 수업 - 깊이 우선 탐색 2  (0) 2023.02.16
C++ 24479 알고리즘 수업 - 깊이 우선 탐색 1  (0) 2023.02.16
C++ 2667 단지번호붙이기  (0) 2023.02.15
C++ 2606 바이러스  (0) 2023.02.14
C++ 7568 덩치  (0) 2023.02.12
'백준' Related Articles more