[BOJ-11724]연결 요소의 개수

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

여러가지 풀이를 할 수 있는 문제이다. 처음으로 생각되는 방법은 BFS 를 이용하는 것과 DFS 를 이용하여 풀이할 수 있다. 다른 방법도 사용할 수 있을 것 같다. 예를 들어 Union-Find 도 사용할 수 있을 것 같다. 

모든 연결되어 있는 정점들을 방문해주면서 한 Connected Component (이하 CC)을 모두 방문이 완료되면 해당 CC에 속한 정점들은 모두 방문했기에 나중에 다시 방문하지 않으며, 이때마다 CC 개수를 +1 하면서 풀 수 있다.

[문제요약]

주어진 무향 그래프 G(V,E) 에서 정점끼리 이어져있는 것을 Connected Component (CC)라 부른다. 이때 구해질 수 있는 CC 의 갯수를 구하는 것이다.

무향그래프이기 때문에 정점A 가 있을 때, 정점 A와 인접한 정점들은 모두 정점A와 같은 CC 집합에 속하게 된다. 그리고 정점A와 인접한 정점B가 있다면, 정점B에 인접한 정점들도 정점A, B와 같은 CC 집합에 속한다. 

[입력]

입력으로 정점의 개수, 간선의 개수 가 주어진다.

간선들의 연결된 정점A 정점B가 주어진다.

[출력]

CC 개수를 출력한다.

[접근방법]

DFS 나 BFS로 정말 빠르게 풀이 할 수 있을 것이라 생각했다. 방문표시하여 O(V+E)로 풀이할 수 있다.

모든 인접한 정점들을 세어주고, 이때 시작정점은 무향그래프이기에 상관이 없다. 대신 모든 정점이 방문표시가 되어야 한다.

정점을 한번 방문할 때마다 CC 개수를 +1 한다. 그리고 인접한 모든 정점을 방문하며, 방문하였다면 방문표시를 하며 누적한다.

#include<cstdio>
#include<vector>
#include<queue>
#define din2(a,b) scanf("%d%d", &a, &b)
#define pb(a) push_back(a)
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
const int S = 1111;
vb vis;
vi g[S];
int v, e;
 
int main(){
    din2(v,e);
    
    vis = vb(v+1, false);
    for(int i = 0 ; i < e ; i++){
        int a,b;
        din2(a,b);
        g[a].pb(b);
        g[b].pb(a);
    }
    queue<int> Q;
    int ans = 0;
    for(int i = 1 ; i <= v ; i++){
        if(vis[i]) continue;
        ans++;
        vis[i] = true;
        Q.push(i);
        while(!Q.empty()){
            int here = Q.front(); Q.pop();
            for(auto there : g[here]){
                if(!vis[there]) vis[there] = true,Q.push(there);
            }
        }
    }
    printf("%d",ans);
    
    return 0;
}

#include<cstdio>
#include<vector>
#define din2(a,b) scanf("%d%d", &a, &b)
#define pb(a) push_back(a)
using namespace std;
typedef vector<int> vi;
typedef vector<bool> vb;
const int S = 1111;
 
vb vis;
vi g[S];
int n,e;
void dfs(int v){
    vis[v] = true;
    for(auto there : g[v]){
        if(!vis[there]) dfs(there);
    }
}
int main(){
    din2(n,e);
    vis = vb(n+1,false);
    for(int i = 0 ; i < e; i++){
        int a,b;
        din2(a,b);
        g[a].pb(b);
        g[b].pb(a);
    }
    
    int ans = 0;
    for(int i = 1 ; i <= n ; i++){
        if(vis[i]) continue;
        ans++;
        dfs(i);        
    }
    printf("%d", ans);
    
    return 0;
}