변수 사이의 관계를 나타내는 방정식이 배열인 경우 이제 각 문자열 방정식[i]은 길이가 4이고 "a==b" 또는 "a!=b"의 두 가지 다른 형식 중 하나를 취합니다. 여기서 및 b는 소문자로, 한 글자로 된 변수 이름을 나타냅니다. 따라서 주어진 모든 방정식을 만족시키기 위해 변수 이름에 정수를 할당할 수 있는 경우에만 참을 찾아야 합니다.
입력이 ["a==b","b==c","a==c"]와 같으면 대답은 true가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
getParent()라는 메서드를 정의합니다. 이것은 문자 x와 맵 m을 사용하며 다음과 같이 작동합니다. -
-
m[x] =x이면 x를 반환합니다.
-
그렇지 않으면 m[x] :=getParent(m[x], m)를 설정하고 m[x]
를 반환합니다. -
기본 방법에서 다음을 수행하십시오 -
-
두 개의 배열을 equal 및 notEqual 정의하고 parent라는 맵을 만듭니다.
-
n :=e의 크기
-
0 ~ n – 1 범위의 i에 대해
-
부모 설정[e[i, 0]] :=e[i, 0], 부모[e[i, 3]] :=e[i, 3]
-
e[i, 1]이 등호이면 i를 등호 배열에 삽입하고, 그렇지 않으면 i를 notEqual 배열에 삽입
-
-
범위 0에서 동일한 크기의 i에 대해 - 1
-
index :=equal[i], u, v를 e[index, 0] 및 e[index, 3]
로 설정 -
부모[getParent(u, 부모)] :=부모[getParent(v, 부모)]
-
-
범위 0에서 notEqual – 1까지의 i에 대해
-
index :=notEqual[i], u, v를 e[index, 0] 및 e[index, 3]
로 설정 -
getParent(u, parent) =getParent(v, parent)인 경우 false를 반환합니다.
-
-
true를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char getParent(char x, map <char, char> m){
if(m[x] == x) return x;
return m[x] = getParent(m[x], m);
}
bool equationsPossible(vector<string>& e) {
vector <int> equal;
vector <int> notEqual;
map <char, char> parent;
int n = e.size();
for(int i = 0; i < n; i++){
parent[e[i][0]]= e[i][0];
parent[e[i][3]]= e[i][3];
if(e[i][1] == '='){
equal.push_back(i);
}else{
notEqual.push_back(i);
}
}
for(int i = 0; i < equal.size(); i++){
int idx = equal[i];
char u = e[idx][0];
char v = e[idx][3];
parent[getParent(u, parent)] = parent[getParent(v, parent)];
}
for(int i = 0; i < notEqual.size(); i++){
int idx = notEqual[i];
char u = e[idx][0];
char v = e[idx][3];
if(getParent(u, parent) == getParent(v, parent)) return false;
}
return true;
}
};
main(){
vector<string> v1 = {"a==b","b==c","a==c"};
Solution ob;
cout << (ob.equationsPossible(v1));
} 입력
["a==b","b==c","a==c"]
출력
true