【算法训练营】等式，道路升级（c++,python实现）

等式

问题描述

有n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。

输入格式

第一行一个整数T，表示数据组数。

接下来会有T组数据，对于每组数据：

第一行是两个整数n,m，表示变量个数和约束条件的个数。

接下来m行，每行三个整数a,b,e，表示第a个变量和第b个变量的关系：

• 若e=0则表示第a个变量不等于第b个变量；
• 若e=1则表示第a个变量等于第b个变量

  输出格式

  输出T行，第i行表示第i组数据的答案。若第i组数据存在一种方案则输出"Yes"；否则输出"No"（不包括引号）。

  样例1输入

  2
  5 5
  1 2 1
  2 3 1
  3 4 1
  1 4 1
  2 5 0
  3 3
  1 2 1
  2 3 1
  1 3 0
  

  样例1输出

  Yes
  No
  

  样例1解释

  一共有2组数据。

  对于第一组数据，有5个约束：

  • 变量1=变量2
  • 变量2=变量3
  • 变量3=变量4
  • 变量1=变量4
  • 变量2≠变量5

    显然我们可以令：

    • 变量1=变量2=变量3=变量4=任意一个数值
    • 变量5=任意一个和变量2不同的数值

      故第一组数据输出"Yes"。 对于第二组数据，有3个约束：

      • 变量1=变量2
      • 变量2=变量3
      • 变量1≠变量3

        由前两个约束可推出变量1=变量3，但第三个约束表明变量1≠变量3，矛盾。

        故第二组数据输出"No"。

        数据范围

        对于10%的数据，n,m ≤ 5，T ≤ 5；

        对于50%的数据，n,m ≤ 1000，T ≤ 10；

        对于100%的数据，1 ≤ n ≤ 300000, m ≤ 500000，1 ≤ a,b ≤ n，T ≤ 100。

        保证所有数据的n总和与m总和不超过500000。

        时间限制：1 s

        空间限制：512 MB

        提示

        [用并查集来维护相等的集合。]

        代码实现

        //#include 
        #include 
        #include 
        #include 
        using namespace std;
        // 并查集
        // ================= 代码实现开始 =================
        const int N = 300005;
        //Father:每个节点的父亲节点
        //Rank:节点的秩
        int Father[N],Rank[N];
        //查找节点x所在集合的根
        //x:节点x
        //返回值:根
        int find(int x){
            return Father[x]==x ? x : Father[x]=find(Father[x]);
        }
        // 给定n个变量以及m个约束，判定是否能找出一种赋值方案满足这m个约束条件
        // n：如题意
        // m：如题意
        // A：大小为m的数组，表示m条约束中的a
        // B：大小为m的数组，表示m条约束中的b
        // E：大小为m的数组，表示m条约束中的e
        // 返回值：若能找出一种方案，返回"Yes"；否则返回"No"（不包括引号）。
        string getAnswer(int n, int m, vector A, vector B, vector E) {
            //初始化
            for(int i = 1; i Rank[setB])
                            swap(setA,setB); // 交换A,B集合
                        Father[setA] = setB;
                        if(Rank[setA] == Rank[setB])
                                Rank[setB]+=1;
                    }
                }
            }
            return "Yes";
        }
        // ================= 代码实现结束 =================
        int main() {
            int T;
            for (scanf("%d", &T); T--; ) {
                int n, m;
                scanf("%d%d", &n, &m);
                vector A, B, E;
                for (int i = 0; i  
           
           
        道路升级
         
           
          
        问题描述
         
            
        Z国有 n 个城市和 m 条双向道路，每条道路连接了两个不同的城市，保证所有城市之间都可以通过这些道路互达。每条道路都有一个载重量限制，这限制了通过这条道路的货车最大的载重量。道路的编号从 1 至 m 。巧合的是，所有道路的载重量限制恰好都与其编号相同。
         
            
        现在，要挑选出若干条道路，将它们升级成高速公路，并满足如下要求：
         
            

        • 所有城市之间都可以通过高速公路互达。
        • 对于任意两个城市 u,v 和足够聪明的货车司机：只经过高速公路从 u 到达 v 能够装载货物的最大重量，与经过任意道路从 u 到达 v 能够装载货物的最大重量相等。（足够聪明的司机只关注载重量，并不在意绕路）

          在上面的前提下，要求选出的道路数目尽可能少。

          求需要挑选出哪些道路升级成高速公路（如果有多种方案请任意输出一种）。

          输入

          第一行 2 个用空格隔开的整数 n,m ，分别表示城市数目、道路数目。

          第 2 行到第 m+1 行，每行 2 个用空格隔开的整数 u,v 描述一条从 u 到 v 的双向道路，第 i+1 行的道路的编号为 i 。

          注意：数据只保证不存在连接的城市相同的道路（自环），并不保证不存在两条完全相同的边（重边）

          输出

          第一行一个整数 k ，表示升级成高速公路的道路数。

          接下来 k 行每行一个整数，从小到大输出所有选出的道路的编号。

          输入样例

          3 3
          1 2
          2 3
          1 3
          

          输出样例

          2
          2
          3
          

          数据范围

          对于 20% 的数据，保证 n≤5，m≤10。

          对于 60% 的数据，保证 n≤1,000，m≤5,000。

          对于 100% 的数据，保证 n≤200,000，m≤400,000。

          时间限制：10 sec

          空间限制：256 MB

          提示

          [提示1：真的可能有多种方案吗？]

          [提示2：k 是否一定为 n-1 呢？（也就是说，选出的道路是否恰好构成了一棵树？）]

          [提示3：这道题和最小生成树有什么关系呢？]

          代码实现

          class UnionSet:
              def __init__(self, n):
                  self.f = [i for i in range(n + 1)]
              def find(self, x):
                  if self.f[x] == x:
                      return x
                  self.f[x] = self.find(self.f[x])
                  return self.f[x]
              def merge(self, x, y):
                  set_x = self.find(x)
                  set_y = self.find(y)
                  if set_x != set_y:
                      self.f[set_x] = set_y
                      return True
                  return False
          def get_answer(n, m, U, V):
              ans = []
              us = UnionSet(n)
              for i in range(m - 1, -1, -1):
                  if us.merge(U[i], V[i]):
                      ans.append(i + 1)
              ans.reverse()
              return ans
          if __name__ == "__main__":
              n, m = map(int, input().split())
              U, V = [], []
              for _ in range(m):
                  u, v = map(int, input().split())
                  U.append(u)
                  V.append(v)
              ans = get_answer(n, m, U, V)
              print(len(ans))
              for edge in ans:
                  print(edge)