Prim.code-snippets

{
	"Prim": {
		"prefix": "Prim",
		"body": [
		  "struct Prim {",
		  "",
		  "    struct Edge {",
		  "",
		  "        ll v, w;",
		  "",
		  "        Edge(ll V = 0, ll W = 0) : v(V), w(W) {}",
		  "",
		  "        bool operator < (const Edge &e) const {",
		  "            return w < e.w;",
		  "        }",
		  "",
		  "    };",
		  "",
		  "    vector < vector < Edge > > adj;",
		  "    vector < ll > marked;",
		  "",
		  "    Prim(ll n = 0){",
		  "        adj = vector < vector < Edge > > (n + 10);",
		  "        marked = vector < ll > (n + 10, 0);",
		  "    }",
		  "",
		  "    void build_adj(int edges, bool is_directed = false){",
		  "        for(int i = 0, u, v, w; i < edges && cin >> u >> v >> w; i++){",
		  "            adj[u].push_back(Edge(v, w));",
		  "            if(!is_directed)",
		  "                adj[v].push_back(Edge(u, w));",
		  "        }",
		  "    }",
		  "",
		  "    ll get_cost(int root){",
		  "        ll cost = 0;",
		  "        priority_queue < Edge > pq;",
		  "        pq.push(Edge(root, 0));",
		  "        while(!pq.empty()){",
		  "            auto [u, curr_cost] = pq.top();",
		  "            pq.pop();",
		  "            // Checking for cycle",
		  "            if(marked[u]) continue;",
		  "            marked[u] = true;",
		  "            cost += curr_cost;",
		  "            for(auto& [v, w] : adj[u]){",
		  "                if(!marked[v])",
		  "                    pq.push(Edge(v, w));",
		  "            }",
		  "        }",
		  "        return cost;",
		  "    }",
		  "",
		  "};"
		],
		"description": "Prim"
	}
}