题目描述(难度困难)

Alice和Bob共有一个无向图,其中包含n个节点和3种类型的边:
类型1:只能由Alice 遍历。
类型2:只能由Bob遍历。
类型3: Alice和Bob都可以遍历
给定一个数组edges ,其中edges[i] = [type_i, u.i, v_i]表示节点ui和v_i之间存在类型为type_i的双向边。
请你在保证图仍能够被Alice和Bob完全遍历的前提下,找出可以删除的最大边数。
如果从任何节点开始, Alice和Bob都可以到达所有其他节点,则认为图是可以完全遍历的。返回可以删除的最大边数,如果Alice和Bob无法完全遍历图,则返回-1

算法(并查集)

1,将整个过程看做加边的操作。先遍历一次边集数组,优先加入类型为3的边。
2.维护两个并查集,分别表示Alice和Bob的连通情况。
3.加类型3的边时,如果发现Alice或Bob不连通(事实上二者应该一致),则两个并查集都进行合并当前边的两个节点;否则,这条边就是冗余的。
4,加类型1或2的边时同理,单独判断Alice或Bob的连通性,操作对应的并查集。
5,最后注意判断Alice和Bob是否都连通。

时间复杂度：O(m+n)
空间复杂度：O(n)

样例

输入样例：
4 6 //节点个数，边的个数
3 1 2
3 2 3
1 1 3
1 2 4
1 1 2
2 3 4
输出样例：
2

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind //并查集
{
public:
    vector<int> f, sz;

    UnionFind(int n)  // 并查集的初始化
    {
        f.resize(n);
        sz.resize(n);
        for (int i=0; i<n; i++)
        {
            f[i] = i;
            sz[i] = 1; // 这里记得把size矩阵初始化为1，公众号上写错了
        }

    }

    int find(int x) //找到根节点
    {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

    void merge(int x, int y)  //合并两棵树
    {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;

        if (sz[fx] < f[fy])
        {
            f[fx] = fy;
            sz[fy] += sz[fx];
        }
        else
        {
            f[fy] = fx;
            sz[fx] += sz[fy];
        }
    }
};

class Solution
{
public:
    int maxNumEdgesToRemove(int n, vector<vector<int> >& edges)
    {
        UnionFind a(n), b(n);
        int ans = 0;
        for (const auto &e:edges)
        {
            int x = e[1]-1, y = e[2]-1;
            if (e[0] != 3) continue;

            if (e[0] == 3)
            {
                if (a.find(x) != a.find(y) || b.find(x) != b.find(y))
                {
                    a.merge(x, y);
                    b.merge(x, y);
                }
                else ans++;
            }
        }

        for (const auto &e : edges)
        {
            int x = e[1]-1, y = e[2]-1;
            if (e[0] == 1)
            {
                if (a.find(x) != a.find(y)) a.merge(x, y);
                else ans++;
            }
            else if (e[0] == 2)
            {
                if (b.find(x) != b.find(y)) b.merge(x, y);
                else ans++;
            }
        }

        if (a.sz[a.find(0)] != n || b.sz[b.find(0)] != n) return -1;  // 通过size矩阵来判断图是否为完全连通的

        return ans;
    }
};

int main()
{
    Solution S;
    vector<vector<int> > edges;
    int n, e; //节点个数，边的个数
    cin >> n >> e;
    for (int i=0; i<e; i++)
    {
        int t,x,y;
        cin >> t >> x >> y;
        vector<int> tmp;
        tmp.push_back(t);
        tmp.push_back(x);
        tmp.push_back(y);
        edges.push_back(tmp);
    }

    int res = S.maxNumEdgesToRemove(n, edges);
    cout << res << endl;
    return 0;
}