Graph 11724

C++ 코드

#include <bits/stdc++.h>
using namespace std;


vector<vector<int>> graph;
vector<bool> vis;


void bfs(int start)
{
    queue<int> q;
    q.push(start);
    vis[start] = true;


    while(!q.empty())
    {
        int current = q.front();
        q.pop();


        for(int next : graph[current])
        {
            if(!vis[next])
            {
                vis[next] = true;
                q.push(next);
            }
        }
    }
}


int main()
{
    int n, m;
    cin >> n >> m;


    graph.resize(n+1);    //정점이 1부터 시작하기때문
    vis.resize(n+1);


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


    int count = 0;


    for(int i = 1; i <= n; i++)    //BFS를 도는횟수를 맞추기위함
    {
        if(!vis[i])
        {
            bfs(i);
            count++;
        }
    }


    cout << count << endl;
    return 0;


}