题目描述
Alice 和 Bob 共有一个无向图,其中包含 n 个节点和 3种类型的边:
类型 1:只能由 Alice 遍历。
类型 2:只能由 Bob 遍历。
类型 3:Alice 和 Bob 都可以遍历。
给你一个数组 edges ,其中 edges[i] = [typei, ui, vi]表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下,找出可以删除的最大边数。如果从任何节点开始,Alice 和 Bob 都可以到达所有其他节点,则认为图是可以完全遍历的。
返回可以删除的最大边数,如果 Alice 和 Bob 无法完全遍历图,则返回 -1
样例
n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
返回2,表示需要最多删除2条边,使得bob和alice都能把图走通
算法 kruskal求最小生成树
思路:
先找出Bob和Alice都能走的边,将端点联通.
公共集合p(表示alice和bob都有的边)大小
P1(表示只有alice能走的边)大小, P2(表示只有bob能走的边)大小++
再考虑只有一个人可以走的边,再做一遍kruskal,将总边数 减去 最后的集合大小即为答案。
由于kruskal求的是最小生成树,至少需要k条边可以构成一个连通图,因此最多可以删除m - k条边。
时间复杂度 O(nlogn)
C++ 代码
const int M = 300100, N = 100010;
class Solution {
public:
struct Edge{
int a, b, c;
bool operator < (const Edge& other) const{
return c < other.c;
}
}E[M];
int m, n, p[N], p1[N], p2[N], res;
int find(int x, int p[])
{
if (x != p[x]) p[x] = find(p[x], p);
return p[x];
}
void kruskal()
{
for (int i = 1; i <= n; i ++)
{
p[i] = i;
p1[i] = i;
p2[i] = i;
}
for (int i = 0; i < m; i ++)
{
int a = E[i].a, b = E[i].b, c = E[i].c;
int pa = find(a, p), pb = find(b, p);
if (pa != pb)
{
p[pa] = pb;
p1[pa] = pb;
p2[pa] = pb;
res ++;
}
}
}
void modify(vector<vector<int>>& edges, int type, int px[])
{
m = 0;
for (auto e:edges)
{
int c = e[0], a = e[1], b = e[2];
int pa = find(a, px), pb = find(b, px);
if (c == type){
if (pa == pb) continue;
E[m ++] = {a, b, c};
}
}
/***
sort(E, E + m);, 不是求权值最小,是求可以联通,因此不用sort,此时时间复杂度O(m)
借用kruskal的思想
评论大佬给出了更简洁的写法qaq
***/
for (int i = 0; i < m; i ++)
{
int a = E[i].a, b = E[i].b, c = E[i].c;
int pa = find(a, px), pb = find(b, px);
if (pa != pb){
px[pa] = pb;
res ++;
}
}
}
bool check(vector<vector<int>>& edges, int p[]){
for (auto e:edges){
int pa = find(e[1], p), pb = find(e[2], p);
if (pa != pb) return false;
}
return true;
}
bool check2()
{
for (int i = 1; i <= n - 1; i ++)
{
int j = i + 1;
int pa = find(i, p), pb = find(j, p);
if (pa != pb) {
pa = find(i, p1), pb = find(j, p1);
if (pa != pb){
pa = find(i, p2), pb = find(j, p2);
if (pa != pb) return false;
}
}
}
return true;
}
int maxNumEdgesToRemove(int x, vector<vector<int>>& edges) {
n = x;
res = 0, m = 0;
for (auto e:edges){
int c = e[0], a = e[1], b = e[2];
if (c == 3) E[m ++] = {a, b, c};
}
kruskal();
modify(edges, 1, p1);
modify(edges, 2, p2);
if (!check(edges, p1) || !check(edges, p2) || !check2()) return -1;
return edges.size() - res;
}
};
其实这题不用这么麻烦,考虑在图能完全遍历的情况下,先统计类型3的边所能连通的点的个数,那么要将所有点连通,就必须每个连通块都用类型1和类型2的边相连,最后统计将所有点连通所需的边,总边数减去所需的边数就是可以去除的边的数目。
对,这里的主要思路就是这样,先联通都能走的点,再联通各自能走的点,将所有的边减去所有用到的边的数量就是答案,只是我是最后判断图是否可以完全遍历
%%,好吧,没有细想,大佬写的很简洁
orz,可以不用sort