19(마지막). 위상정렬, SCC, 2-SAT

19.md

0.01MB

0. 복습
1. 위상정렬

1005번을 한번 보자.

그림의 노드들을 정렬한다고 치면 1, 2, 3, 4 혹은 1, 3, 2, 4순으로 정렬할 수 있다.

건물을 지을 때 1번은 2, 3번보다 앞에 있어야 하고 1, 2, 3번은 4번 앞에 있어야 한다.

DAG, Directed Assigned Graph일때만 위상정렬이 가능하다.
사이클이 존재하지 않는 유향 그래프라는 뜻이다.

DFS 종료의 역순은 위상정렬 순이다.

DFS를 활용한 위상정렬:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int T, N, K, W;
vector<int> g[100001];
int t[1001];
int fin[1001];
bool visited[100001];
vector<int> st;
void DFS(int n){
    visited[n] = true;
    for(int i=0; i<g[n].size(); ++i){
        int next = g[n][i];
        if(!visited[next]){
            DFS(next);
        }
    }
    st.push_back(n);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    while(T--){
        memset(visited, 0, sizeof(visited));

        memset(fin, 0, sizeof(fin));
        st.clear();
        for(int i=0; i<1001; ++i) g[i].clear();

        cin >> N >> K;
        for(int i=1; i<=N; ++i){
            cin >> t[i];
        }
        for(int i=0; i<K; ++i){
            int x, y; cin >> x >> y;
            g[x].push_back(y);
        }
        cin >> W;
        for(int i=1; i<=N; ++i){
            if(!visited[i]){
                DFS(i);
            }
        }
        reverse(st.begin(), st.end());
        for(auto n : st){
            fin[n] += t[n];
            for(auto next : g[n]){
                fin[next] = max(fin[next], fin[n]);
            }
        }
        cout << fin[W] << '\n';
    }
}

참고 : 1005, 1516, 2252

2. SCC

강한연결요소, 강결합 컴포넌트, Strong Connected Component

아까 위상정렬은 DAG에서만 가능하다고 했는데, 사이클이 있을 때 SCC 집합으로 위상정렬을 한다.

DFS 종료 역순으로, 역방향 그래프에서 DFS를 한번 더 돌리면 SCC가 위상정렬순으로 묶인다.

코드 : (with 코사라주 알고리즘)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int V, E;
vector<int> G[10001];
vector<int> RG[10001];
int visited[10001];

vector<int> st;

vector<vector<int> > scc;

void DFS(int n){
    visited[n] = true;
    for(int i=0; i<G[n].size(); ++i){
        if(!visited[G[n][i]]){
            DFS(G[n][i]);
        }
    }
    st.push_back(n);
}
void DFS2(int n){
    visited[n] = true;
    for(int i=0; i<RG[n].size(); ++i){
        if(!visited[RG[n][i]]){
            DFS2(RG[n][i]);
        }
    }
    scc.back().push_back(n);
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> V >> E;
    for(int i=0; i<E; ++i){
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        RG[b].push_back(a);
    }
    for(int i=1; i<=V; ++i){
        if(!visited[i]) DFS(i);
    }
    reverse(st.begin(), st.end());
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<st.size(); ++i){
        int n = st[i];
        if(visited[n]) continue;
        scc.push_back(vector<int>()); // 새로운 scc 생성
        DFS2(n); // 역방향 그래프에서 DFS를 돌리면서 만나는 모든 정점을 새로운 SCC에 담아줌.
    }

    for(int i=0; i<scc.size(); ++i){
        sort(scc[i].begin(), scc[i].end());
    }
    sort(scc.begin(), scc.end());

    cout << scc.size() << '\n';
    for(int i=0; i<scc.size(); ++i){
        for(int j=0; j<scc[i].size(); ++j){
            cout << scc[i][j] << ' ';
        }
        cout << -1 << '\n';
    }
}

참고 : 2150, 4196

3. 2-SAT

11277번을 보면 2-SAT과 2-CNF에 대한 설명이 있다.

여기서 x 논리합 y는 x가 거짓이면 y는 반드시 참이어야 하고, y가 거짓이면 x가 반드시 참이어야 한다. 이렇게 하나의 논리합에 두가지 if식이 나오고, 이를 그래프로 연결해서 scc를 찾고, 답을 유추해낼 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MN = 10000;
int N, M;
vector<int> G[2*MN+1];
vector<int> RG[2*MN+1];
int visited[2*MN+1];

vector<int> st;

vector<vector<int> > scc;

void DFS(int n){
    visited[n] = true;
    for(int i=0; i<G[n].size(); ++i){
        if(!visited[G[n][i]]){
            DFS(G[n][i]);
        }
    }
    st.push_back(n);
}
void DFS2(int n){
    visited[n] = true;
    for(int i=0; i<RG[n].size(); ++i){
        if(!visited[RG[n][i]]){
            DFS2(RG[n][i]);
        }
    }
    scc.back().push_back(n);
}
int ToNot(int a){
    if(a<=N) a+=N;
    else a-=N;
    return a;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    for(int i=0; i<M; ++i){
        int a, b; cin >> a >> b;
        if(a<0) a=-a+N;
        if(b<0) b=-b+N;
        G[ToNot(a)].push_back(b);
        G[ToNot(b)].push_back(a);
        RG[b].push_back(ToNot(a));
        RG[a].push_back(ToNot(b));
    }
    for(int i=1; i<=2*N; ++i){
        if(!visited[i]) DFS(i);
    }
    reverse(st.begin(), st.end());
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<st.size(); ++i){
        int n = st[i];
        if(visited[n]) continue;
        scc.push_back(vector<int>()); // 새로운 scc 생성
        DFS2(n); // 역방향 그래프에서 DFS를 돌리면서 만나는 모든 정점을 새로운 SCC에 담아줌.
    }
    memset(visited, 0, sizeof(visited));
    for(int i=0; i<scc.size(); ++i){
        for(int j=0; j<scc[i].size(); ++j){
            int n=scc[i][j];
            if(visited[ToNot(n)]==true) {
                cout << 0 << '\n';
                return 0;

            }
            visited[n]=true;
        }
        for(int j=0; j<scc[i].size(); ++j){
            visited[scc[i][j]] = false;
        }
    }
    cout << 1 << '\n';
}

참고 : 11277, 11278, 11280, 11281