코딩테스트준비

백준 11724. 연결 요소의 개수 (그래프)

haeullee 2023. 7. 27. 23:38

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

그래프를 이용한 bfs, 재귀 dfs, 비재귀 dfs로 풀 수 있다. 

 

1. bfs

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int> adj[1002];
int u, v;
int vis[1002];
queue<int> _queue;
int main()
{           
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
 
    cin >> n >> m;

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

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        _queue.push(i);
        vis[i] = true;
        ans++;
        while(!_queue.empty())
        {
            int cur = _queue.front();
            _queue.pop();

            for(auto nxt: adj[cur])
            {
                if(vis[nxt]) continue;
                _queue.push(nxt);
                vis[nxt] = true;
            }
        }
    }
    
    cout << ans;

}

 

2. 재귀 dfs

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
int u, v;
vector<int> adj[1002];
int vis[1002];

void dfs(int cur)
{
    vis[cur] = true;
    for(auto nxt: adj[cur])
    {
        if(vis[nxt]) continue;
        dfs(nxt);
    }
}

int main()
{           
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
 
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        ans++;
        dfs(i);  
    }

    cout << ans;

    

}

 

3. 비재귀 dfs

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, m;
int u, v;
vector<int> adj[1002];
int vis[1002];
stack<int> _stack;

int main()
{           
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
 
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(vis[i]) continue;
        ans++;
        _stack.push(i);
        vis[i] = true;

        while(!_stack.empty())
        {
            int cur = _stack.top();
            _stack.pop();

            //if(vis[cur]) continue;
            for(auto nxt: adj[cur])
            {
                if(vis[nxt]) continue;
                _stack.push(nxt);
                vis[nxt] = true;
            }

        }
    }

    cout << ans;
  
}