백준 11724번(연결 요소의 개수), 언어 : C++

 

 

문제 링크 : https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

인접 리스트 방식으로 그래프를 표현했다.

오랜만에 알고리즘 하려니 엄청 어색하네.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
vector<int>adj[1001];
bool vis[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int vertex, edge;
    cin >> vertex >> edge;

    int v1, v2;
    for(int i =0; i < edge; i++) {
        cin >> v1 >> v2;
        adj[v1].push_back(v2);
        adj[v2].push_back(v1);
    }

    queue<int> q;

    int cnt = 0;
    for(int i = 1; i <= vertex; i++) {
        if(vis[i] == true) continue;
        q.push(i);
        vis[i] = true;
        cnt += 1;
        
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            for(auto nxt : adj[cur]) {
                if(vis[nxt] == true) continue;
                q.push(nxt);
                vis[nxt] = true;
            }
        }

    }

    cout << cnt;

    return 0;
}