小明の雜貨鋪

Minimum Spanning Tree 构建最小生成树，求最小生成树的边权之和。 Kruskal (DSU) 思路 按边权从小到大的顺序开始合併连通图，如果没有环，那么它一定是最小生成树的一条边。时间复杂度 Θ(mlog⁡m)\Theta(m\log m)Θ(mlogm)，空间复杂度 Θ(m)\Theta(m)Θ(m)。 12345678910111213141516171819202122232425int fa[N];inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }inline void uno(int x, int y) { fa[find(x)] = find(y); }void eachT() { int n = read(); init(n); ...

Bipartite Graph 二分图 中的点由两个集合组成，且两个集合内部没有边。二分图不存在长度为奇数的环。 Check whether a given graph is Bipartite or not (Backtracking algorithm m coloring problem) 如果两个集合中的点分别染成黑色和白色，二分图中的每一条边都一定是连接一个黑色点和一个白色点。 1234567891011121314151617vector<int> E[N];int color[N];bool bipartite(int u) { // 判断是否是二分图 for (auto v : E[u]) { if (color[v] == color[u]) return 0; // 颜色冲突 if (color[v] == 0) { color[v] = -color[u]; if (!bipartite(v)) return 0; //...

Directed Acyclic Graph Topological Sorting 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859vector<int> E[N];int deg[N]; // 入度int dp[N]; // 到达某点的最大点权和inline bool topo(int n) { for (int u = 1; u <= n; ++u) { for (auto v : E[u]) deg[v] += 1;// 统计入度 } priority_queue<int> Q; vector<int> paths; // 记录排序结果 int cnt = 0, flag = 1; // 用于判断排序方式是否惟一 ...