唔 不能这样了 每日一题 链接:https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/

题目大意：一个图 分三种边 A能走的 B能走的 都能走的 问在A B 从任何点出发都能遍历全图的条件下 至多删除几条边

思考过程：leetcode上标了困难 一开始觉得难 觉得将AB放在哪里开始遍历这个图比较好 已经不知道多少天没写过代码了 后来觉得不对 如果两个点之间有都能走的线 那么两点之前其余的线就是多余的 进一步思考 如果两个结点之间是连通的（都能走的线） 那么这两个结点之间的所有其余线都能删除
最后思考：1.删除的线必须是A能走的线/B（不对 这个图必须通过都能走的线连通
2.删除线的数目 应该=总线数目-必要存在线的数目 即用最少的全能线连接所有节点（n-1）
先用这种思考写一下试试行不行

结果是不行 样例1就挂了
进一步更正想法 应当是每个结点具有双向边/一条A边一条B边
新想法：从第一个节点开始BFS两次 两个角色分别一次 能够全部遍历进入下一步 否则输出-1
找出仅用全能边连接的图。。。

可以 放弃了 看题解了 原来是并查集 思路写代码里了

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

class UnionFind
{
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;

public:
    //初始化函数
    UnionFind(int _n) : n(_n), setCount(_n), parent(_n), size(_n, 1)
    {
        iota(parent.begin(), parent.end(), 0);
    }
    //寻找连通分量祖先
    int findset(int x)
    {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }
    //合并
    bool unite(int x, int y)
    {
        x = findset(x);
        y = findset(y);
        if (x == y)
        {
            return false;
        }
        if (size[x] < size[y])
        {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y]; //该连通数加
        --setCount;         //连通分量-1
        return true;
    }
    //判断是否连通
    bool connected(int x, int y)
    {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

class Solution
{
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>> &edges)
    {
        UnionFind ufa(n), ufb(n);
        int ans = 0;
        //结点从0开始
        for (auto &edge : edges)
        {
            edge[1]--;
            edge[2]--;
        }
        //处理公共边
        for (const auto &edge : edges)
        {
            if (edge[0] == 3)
            {
                if (!ufa.unite(edge[1], edge[2]))
                    ans++; //多余边
                else
                    ufb.unite(edge[1], edge[2]); //复制
            }
        }
        //处理独占边
        for (const auto &edge : edges)
        {
            if (edge[0] == 1)
            {
                if (!ufa.unite(edge[1], edge[2]))
                {
                    ans++;
                }
            }
            else if (edge[0] == 2)
            {
                if (!ufb.unite(edge[1], edge[2]))
                {
                    ans++;
                }
            }
        }
        //判断是否连通
        if (ufa.setCount != 1 || ufb.setCount != 1)
        {
            return -1;
        }
        return ans;
    }
};