SCC, 강한 연결 요소, 2-SAT
SCC와 2-SAT
SCC와 함께 배우는 2-satisfiability problem(2 SAT)이라는 알고리즘이 있습니다. 일단 SCC를 배우면 2 SAT 이해와 구현은 쉽기 때문에 SCC부터 설명하도록 하겠습니다.
SCC (Strongly Connected Component, 강한 연결 요소)
SCC는 유향그래프(Direct graph, 방향이 있는 그래프)에서 cycle을 찾는 알고리즘입니다. cycle이 무엇인지 알기 위해 백준 scc 문제에 있는 이미지를 볼까요?
{a,b,e}는 a,b,e중 어느 노드에서도 다른 노드로 갈 수 있기 때문에 cycle입니다. {a,b,e}를 포함하여 4개의 cycle을 볼 수 있습니다.
scc를 구하는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 있는데, 저는 타잔 알고리즘 코드를 보여드리도록 하겠습니다. (복잡도는 둘다 $ O(V+E) $ 로 동일합니다. 타잔 알고리즘의 경우 구해진 scc 결과를 reverse하면 위상정렬한 DAG의 결과가 나오기 때문에 조금 더 범용적입니다.)
알고리즘 개관은 다음과 같습니다.
1. 한번의 dfs를 통해 scc를 구합니다.
1-1. 스택에 쌓인 순서를 파악하기 위해 dfs_num을 저장합니다. 그리고 스택에 쌓아 줍시다.
1-2. DSU 알고리즘과 유사하게, 각 그룹에 부모를 설정합니다. DSU와 마찬가지로 초기 노드의 부모는 자기 자신입니다.
1-3. 인접한 노드에 방문하지 않은 노드가 있다면 dfs 탐색을, 방문했지만 다른 scc 그룹에 속하지 않은 노드가 있다면 해당 노드의 dfs_num을 확인합니다.
1-4. 1-3에서 확인한 dfs_num 중 가장 작은 dfs_num이 본인이라면 해당 노드를 부모로 하는 scc 그룹화가 완료되었다고 할 수 있습니다.
이제 코드를 봅시다.
class SCC{
private:
vector<vi> graph;
vector<vi> scc;
vi idx,fin;
int n,m;
int dfs_num;
vi st;
int dfs(int x){
idx[x]=++dfs_num;
st.push_back(x);
int par=idx[x];
for(int adj:graph[x]){
if(idx[adj]==0) par=min(par,dfs(adj));
else if(fin[adj]==0) par=min(par,idx[adj]);
}
if(par==idx[x]){
vi grp;
while(!st.empty()){
int t=st.back(); st.pop_back();
fin[t]=1;
grp.push_back(t);
if(t==x) break;
}
scc.push_back(grp);
}
return par;
}
public:
SCC(){
dfs_num=0;
cin>>n>>m;
graph.resize(n+5);
idx.resize(n+5,0);
fin.resize(n+5,0);
for(int i=0;i<m;i++){
int a,b; cin>>a>>b;
graph[a].push_back(b);
}
}
void get_ans(){
for(int i=1;i<=n;i++){
if(idx[i]) continue;
dfs(i);
}
for(vi &xx:scc) sort(xx.begin(),xx.end());
sort(scc.begin(),scc.end(),[&](const vi &v1, const vi &v2){
return v1[0]<v2[0];
});
cout<<scc.size()<<'\n';
for(vi xx:scc){
for(int yy:xx) cout<<yy<<" ";
cout<<-1<<'\n';
}
}
};
백준 2150 Strongly Connected Component 의 정답코드입니다.
2-SAT (2 Satisfiable problem)
$ F = (!x_1 \ or \ x_2) \ and \ (x_1 \ or \ !x_2) \ and \ (x_1 \ or \ x_3) \ and \ !x_1 \ and \ x_2 $ 가 참을 만족하도록 하는 $x_1,x_2,x_3$를 찾을 수 있을까요?
2 SAT은 다시 말해서, 이러한 2가지 결과(boolean)을 갖는 관계식이 성립할 수 있는지, 그리고 성립한다면 그 해를 찾는 알고리즘입니다.
우리는 2 SAT 문제를 방향그래프로 바꾸어 생각할 수 있습니다. $ x_1,x_2,…,x_n $ 의 변수로 이루어진 관계식이 있다고 생각해봅시다. 그리고 {$ x_1,x_2,…,x_n $} , {$ !x_1,!x_2,…,!x_n $} 두 집합으로 이루어진 그래프를 생각해봅시다.
이제 감이 오시나요? 우리는 $\rightarrow$ 을 이용하여 그래프를 그릴 수 있으며, x_i와 !x_i가 같은 scc에 포함된다면 이는 관계식을 만족시키는 해가 없다는 말과 동치가 됩니다. ($ a \ or \ b = (!a \rightarrow b) \ and \ (!b \rightarrow a) $ 로 변환 가능)
해가 존재하는 경우 어떻게 해를 찾을 수 있을까요? 들어오는 간선이 없는 노드의 경우에는 false라고 가정하면 아무런 문제가 없습니다. ($p \rightarrow q$)에서 p가 false라고 해도 q에는 영향을 주지 않죠. 그렇게 되면 $!p$는 당연히 true가 되겠군요. 이러한 방식을 계속 하다 보면 하나의 해를 찾을 수 있습니다.
위의 과정을 dfs 탐색을 한번 더 하는 것 보다 쉽게 구현할 수 있습니다. $p$, $!p$ 둘 중에 하나가 결정되기 전에는 둘 다 어떤 값을 갖아도 무방합니다. 둘 중에 먼저 결정되는 노드가 무엇인지만 파악하면 됩니다.
즉, $p$와 $!p$ 에 dfs_num을 비교하여 둘 중에 dfs_num이 더 큰 수가 위상정렬 결과 먼저 나오는 노드이므로 거짓입니다. 물론 이 방식 이외에도 다른 해가 존재할 수 있습니다만, 고려할 필요는 없습니다. 코드는 scc와 동일하니 넘어가도록 하겠습니다.
