반응형
어떻게 보면 혼란스러울 수 있는데!
사실 연결돼 있는 노드 집합의 개수를 찾는 방식과 똑같다 ㅎㅎ
2021/01/22 - [Studying 📖/알고리듬(thm) 공부 🌱] - [백준 11724번 연결 요소의 개수(BFS, DFS)/ C++]
위 글과 비슷한 방식!🐶👍🏻
#include <iostream>
#include <vector>
using namespace std;
vector<int> connection[1002];
vector<bool> vis(1002, false);
void dfs(int v)
{
vis[v] = true;
for (int i = 0; i < connection[v].size(); i++) {
int to = connection[v][i];
if (!vis[to]) {
dfs(to);
}
}
}
int main()
{
int t, n;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
connection[i].clear();
vis[i] = false;
int v;
cin >> v;
connection[i].push_back(v);
}
int count = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
count++;
dfs(i);
}
}
cout << count << "\n";
}
return 0;
}
반응형
'Algorithm 💫 > Problem Solving' 카테고리의 다른 글
[프로그래머스 / python3 / level2] [카카오 3차] 방금그곡 (0) | 2021.08.26 |
---|---|
[백준 4963번 섬의 개수(DFS)/ C++] (0) | 2021.01.26 |
[백준 1707번 이분 그래프(DFS)/ C++] (0) | 2021.01.22 |
[백준 11724번 연결 요소의 개수(BFS, DFS)/ C++] (0) | 2021.01.22 |
[백준 2745번 진법 변환 / C++] (0) | 2021.01.21 |
댓글