问题
本题其实就是三个问题。求最小生成树、不含某条边的最小生成树（可能有也可能没有），一定含某条边的最小生成树。详细分析可见LeetCode上的题解。
解决
因为本题考查的是边，因此用针对边的Kruskal算法即可，这样都不用转换图的表示形式，直接用给定的边集即可。
Kruskal其实属于贪心算法。
Kruskal算法中加入新边时需要考查两个点是否已经被连接，根据网上资料，这个问题可用并查集高效解决。
最后，在代码实现上，我写了一个Kruskal类和一个DSU（Disjoint Set Union，并查集）类（带路径压缩）。借助二者即可完成Solution类。
之所以DSU类中写了两个findFather，是因为我一开始写的是非递归的版本（数据大时可防止爆栈），但是可能因为其中使用的Stack增加了时间复杂度，LeetCode上超时。之后改成了递归版本即可通过。整个速度稍慢，不知道是不是因为使用了很多STL模板而LeetCode没开O2优化的原因。
class DSU // Disjoint Set Union
{
vector<int> fathers;
public:
DSU(const int n)
{ // initialize
for (int i = 0; i < n; i++)
fathers.push_back(i);
}
DSU() = default;
void init(const int n)
{
if (fathers.size())
return;
for (int i = 0; i < n; i++)
fathers.push_back(i);
}
int findFather(const int x)
{
if (fathers[x] == x)
return x;
else
{
fathers[x] = findFather(fathers[x]);
return fathers[x];
}
}
int findFather2(const int x)
{
int now = x, father = fathers[x];
stack<int> to_modify;
while (now != father)
{
to_modify.push(now);
now = father;
father = fathers[father];
}
while (!to_modify.empty())
{
fathers[to_modify.top()] = father;
to_modify.pop();
}
return father;
}
bool unionTwo(const int x, const int y)
{
int x_father = findFather(x), y_father = findFather(y);
if (x_father == y_father)
return false;
else
{
fathers[y_father] = fathers[x_father];
return true;
}
}
};
class Kruskal
{
int n;
vector<vector<int>>& edges;
vector<int> tree;
int exist_edge;
int del_edge;
int total;
DSU dsu;
public:
Kruskal() = default;
Kruskal(const int _n, vector<vector<int>>& _edges, const int _exist_edge, const int _del_edge):
n(_n), edges(_edges), exist_edge(_exist_edge), del_edge(_del_edge), total(0)
{
dsu.init(n);
if (exist_edge != -1)
{
tree.push_back(exist_edge);
auto &e = edges[exist_edge];
total += e[2];
dsu.unionTwo(e[0], e[1]);
}
mst();
}
int mst()
{
for (int i = 0; i < edges.size(); i++)
{
if (i != exist_edge && i != del_edge)
{
if (dsu.findFather(edges[i][0]) != dsu.findFather(edges[i][1]))
{
tree.push_back(i);
dsu.unionTwo(edges[i][0], edges[i][1]);
total += edges[i][2];
}
}
if (tree.size() == n - 1)
return total;
}
total = -1;
return -1;
}
int total_value()
{
return total;
}
};
class Solution
{
static bool cmp(vector<int>& x, vector<int>& y)
{
return x[2] < y[2];
}
public:
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges)
{
for (int i = 0; i < edges.size(); i++)
{
edges[i].push_back(i); // e[i] = {from, to, w, index}
}
sort(edges.begin(), edges.end(), cmp);
vector< vector<int> > ans(2);
int mst = Kruskal(n, edges, -1, -1).total_value();
for (int i = 0; i < edges.size(); i++)
{
auto& e = edges[i];
int mst_del_e = Kruskal(n, edges, -1, i).total_value();
if (mst_del_e == -1 || mst_del_e > mst)
ans[0].push_back(e[3]);
else
{
int mst_exist_e = Kruskal(n, edges, i, -1).total_value();
if (mst_exist_e == mst)
ans[1].push_back(e[3]);
}
}
return ans;
}
};