讨论/《2021 春招冲刺攻略》 - 990. 等式方程的可满足性/
《2021 春招冲刺攻略》 - 990. 等式方程的可满足性
共 2 个回复

并查集 数组简单实现 Java

image.png

class Solution {
    public boolean equationsPossible(String[] equations) {
      final UnionFind uf = new UnionFind(26);
      for (int i = 0; i < equations.length; i++) {
        /*["a==b","b!=a"]*/
        String equation = equations[i];
        if (equation.charAt(1) == '=') {
          uf.union(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
        }
      }
      for (int i = 0; i < equations.length; i++) {
        String equation = equations[i];
        if (equation.charAt(1) != '=') {
          if (uf.isUnion(equation.charAt(0) - 'a', equation.charAt(3) - 'a')) return false;
        }
      }
      return true;
    }

    /** 并查集 */
    private class UnionFind {
      private int[] parent;

      public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < parent.length; i++) {
          parent[i] = i;
        }
      }

      /**
       * 连接两个元素
       *
       * @param p index
       * @param q index
       */
      void union(int p, int q) {
        if (parent[p] == parent[q]) return;
        for (int i = 0; i < parent.length; i++) {
          if (i != p && parent[i] == parent[p]) {
            parent[i] = parent[q];
          }
        }
        parent[p] = parent[q];
      }

      /**
       * 判断 是否相连
       *
       * @param p index
       * @param q index
       * @return
       */
      Boolean isUnion(int p, int q) {
        return parent[p] == parent[q];
      }
    }
  }
1

C++ 并查集 100% KILL

class Solution {
public:

    // N is the number of the node of graphics.
struct m_union_find
{
	// the parents node.
    
	int parent[26];
	// rank is used to zip the deeth of tree;
	int rank[26];

	// initializing
	m_union_find()
	{
		for (int i = 0; i < 26; ++i)
		{
			parent[i] = i;
			rank[i] = 0;
		}
	}

	// find parents.
	int find(int a)
	{
		if (parent[a] == a)
		{
			return a;
		}
		parent[a] = find(parent[a]);
		return parent[a];
	}

	// merge (union is the key word of c++).
	bool merge(int a, int b)
	{
		int p_a = find(a);
		int p_b = find(b);
		if(p_a == p_b)
		{
			return false;
		}
		if (rank[p_a] > rank[p_b])
		{
			parent[p_b] = p_a;
		}
		else if (rank[p_a] < rank[p_b])
		{
			parent[p_a] = p_b;
		}
		else
		{
			parent[p_b] = p_a;
			++rank[p_a];
		}
		return true;
	}
};
bool equationsPossible(std::vector<std::string>& equations)
{
	m_union_find M;

	for (std::string& s : equations)
	{
		if (s[1] == '=')
		{
			M.merge(s[0] - 'a', s[3] - 'a');
		}
	}

	for (std::string& s : equations)
	{
		if (s[1] == '!' && M.find(s[0] - 'a') == M.find(s[3] - 'a'))
		{
			return false;
		}
	}
	return true;
}
};