11724 연결 요소의 개수

문제 링크

• 나의 풀이

유니온 파인드를 통해 연결된 요소의 최적화된 트리를 만들고 해당 요소를 순회하며 루트의 갯수를 세어 답을 제출하였다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> tree;

int find(int x)
{
    if (x == tree[x])
        return x;

    return tree[x] = find(tree[x]);
}

void merge(int x, int y)
{
    int u = find(x);
    int v = find(y);

    if (u == v)
        return;

    tree[u] = v;
}

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

    vector<vector<int>> lst;
    int ret = 0, a, b;

    cin >> N >> M;
    tree.resize(N + 1);
    for (int i = 1; i < N + 1; i++)
        tree[i] = i;

    for (int i = 0; i < M; i++)
    {
        cin >> a >> b;
        merge(a, b);
    }
    int piv = 0;
    vector<int> chk;
    chk.resize(N + 1);
    for (int i = 1; i < N + 1; i++)
    {
        int k = find(i);
        if (!chk[k])
        {
            ret += 1;
            chk[k] = 1;
        }
    }

    cout << ret << "\n";
}

• 다른사람 풀이

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

int v,e;
vector<int> adj[1001];
bool vis[1001];
int dfs(){ // 연결 요소의 갯수를 반환
  int ret = 0;
  stack<int> s;
  for(int i = 1; i <= v; i++){
    if(vis[i]) continue;
    ret++;
    s.push(i);
    vis[i] = true;
    while(!s.empty()){
      int cur = s.top();
      s.pop();
      for(int i = 0; i < adj[cur].size(); i++){
        int nxt = adj[cur][i];
        if(vis[nxt]) continue;
        s.push(nxt);
        vis[nxt] = true;
      }    
    }
  }
  return ret;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> v >> e;
  while(e--){
    int a,b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  cout << dfs();
}