11724 연결요소의 개수 C++ 문제풀이

위 문제는 BFS 혹은 DFS 로 간단히 풀리는 문제다.

 

아래 코드는 BFS로 푼 형태이고

코드의 핵심은 BFS이다.

BFS는 자료구조 큐를 FIFO로서 이용하는것과,

큐 자료구조를 순회하기 위한 iterator를 자주 써보는것.

지나갔던 Vertex에 대해서 visited 처리하는 것이 무엇보다 중요함!

#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include <algorithm>
#include <bits/stdc++.h>


using namespace std;
vector<int> ll_edge[1001];
bool visited[1001];
int cnt;


void bfs(int start,int N)
{
    queue<int>q;
    q.push(start);

    visited[start] = true;
	while (!q.empty()) 
    {
		int cur = q.front();
		q.pop();

		vector<int>::iterator it;
        for(it=ll_edge[cur].begin();it!=ll_edge[cur].end();it++)
        {
            int temp = *it;
			if (visited[temp] == false)
            {
				visited[temp] = true;
				q.push(temp);
			}
		}
	}

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int M;
    int temp_start_point,temp_end_point;
     
    cin >> N;
    cin >> M;

    for(int i=0;i<M;i++)
    {
        cin >> temp_start_point;
        cin >> temp_end_point;
        ll_edge[temp_start_point].push_back(temp_end_point);
        ll_edge[temp_end_point].push_back(temp_start_point);

    }

    for(int i=1;i<=N;i++)
    {
        if(visited[i]!=true)
        {
            cnt++;
            bfs(i,N);
        }
    }

    cout << cnt;
  


    return 0;
}