김미썸코딩

DFS, BFS, Union-Find를 사용하여 풀수 있는 문제다. 1. DFS(재귀) #include #include #include //memset using namespace std; const int MAX = 100 + 1; int N, M; int adjacent[MAX][MAX];// 1이면 연결됨을 의미 bool visited[MAX]; int cnt; // DFS 재귀 void DFS(int v) { cnt++; for (int i = 1; i > N >> M; for (int i = 0; i > from >> to; adjacent[from][to] = 1; adjacent[to][from] = 1; } visited[1] = 1;..

Union-find를 활용하는 문제다 *** Union-find 개념 *** https://gimmesome.tistory.com/34?category=1103655 [1주차] Union-find 학교에서 알고리즘을 배울때도 Union-find는 따로 배운적은 없고 기억을 더듬어 보면... 다른 알고리즘에 포함되어 있는 걸로 배웠던것 같다. Union-find 강의를 보면서 관련 문제들을 풀어보다가 Union gimmesome.tistory.com 필요한 배열 2개 --> 부모노드가 담길 arr, 노드별 친구 비 A merge함수에서 두 노드의 A의 값(친구비)을 비교하고 더 싼 친구비를 가진 노드를 부모노드로 해서 합친다. 트리가 몇개가 되든 각 트리의 루트노드(트리에서 가장 친구비가 가장 작음)들은 ..