[백준 1108] 검색 엔진

문제

https://www.acmicpc.net/problem/1108

 

알고리즘

SCC

 

풀이

점수가 무한대로 늘어나는 것을 방지하기 위해 두 정점에 대해 직간접적 연결이 없을 때에만 점수를 더해준다고 합니다. 직간접 연결을 확인하려면 그래프에서 사이클을 확인해야 하고 사이클을 확인하는 알고리즘인 SCC를 떠올릴 수 있습니다. 

 

SCC알고리즘 사용 이후, 모든 간선을 검사하며 두 정점의 $sccid$가 다르다면 $sccadj$에 실제 간선을 추가해줍시다. 이 이유는 하나의 SCC로 묶인 정점들끼리도 점수가 다를 수 있기 때문입니다. 단, $cache$를 갱신하는 과정은 위상정렬상 앞에 있는 순서부터 뒤에 있는 순서로 갱신해나가야 하므로, vector<vector<pii>>형태를 사용한 것에 주목합시다.

예를 들어 scc_adj[a] = {b, c} 일 때, a는 위상정렬의 순서를 의미하고 b, c는 실제 간선을 나타냅니다.  이후엔 이전의 문제들과 마찬가지로 for문의 역순으로 $cache$를 갱신해나가면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;
map<string, int> STOI;

int N,cnt,num,VC,SC;
string u, v,want;

vector<vector<int>> adj;
vector<vector<pii>> scc_adj;
vector<int> sccid, discovered;

vector<long long> cache;
stack<int> st;

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        SC++;
    }
    return ret;
}

int main() {
    FAST;
    cin >> N;
    adj.resize(2501);
    rep(i, N) {
        cin >> u >> cnt;
        if (STOI.find(u) == STOI.end()) STOI[u] = num++;
        rep(j, cnt) {
            cin >> v;
            if (STOI.find(v) == STOI.end()) STOI[v] = num++;
            adj[STOI[v]].emplace_back(STOI[u]);
        }
    }
    cin >> want;
    if (STOI.find(want) == STOI.end()) STOI[want] = num++;

    discovered = sccid = vector<int>(2501, -1);
    rep(i, num) if (discovered[i] == -1) scc(i);

    scc_adj.resize(2501);
    rep(here,num) for(auto there : adj[here]){
        if (sccid[here] != sccid[there])
            scc_adj[sccid[here]].emplace_back(here, there);
    }

    int wt =STOI[want];
    cache.resize(2500, 1);
    for (int i = SC-1;i;--i) {
        for (auto [a,b] : scc_adj[i]){
            cache[b] += cache[a];
        }
    }
    cout << cache[wt];
    return 0;
}