GeeksForGeeks

When to use get MST of undirected & weighted Graph Idea maintain two sets of vertices (1: MST, 2: not visited) find cut vertex minimum weight in each loop until all vertices be included in MST 📝 cut vertex: connect vertex which connects two disjoint subsets Algorithm (1) Create key-value table (vertex - weight) , empty MST Set (2) initialize first value of key as '0' to visit first, remain key a..

🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..

이론 정리한지 1년이 넘어서 풀어보는 예제 🔒 문제 위상 정렬 순서에 맞는 answer vector를 리턴하라. 🔑 풀이 class Solution{ public: vector topoSort(int V, vector adj[]) { int * indegree = new int[V]{0}; std::vector answer; // initialize indegree array for (int i = 0; i < V; i++) { for (const auto& adjacentVertex : adj[i]) { indegree[adjacentVertex]++; } } std::queue queue; // indegree 0 찾고 넣기 for (int i = 0; i < V; i++) { if(indegree[..