[Baekjoon - 10287] Spy Network

난이도: Platinum I

 

태그

• Strongly Connected Component
• Dynamic Programming (on SCC)
• Greatest Common Divisor

 

풀이

1. 어떤 사이클에 있는 사람들이 가지게 되는 정보는?

충분히 많은 시간이 지나게 되면, 사이클에 있는 모든 사람들이 동일한 수를 가지게 됩니다.

또한, 이 수는 모든 사람들이 초기 상태에 가지고 있던 수의 GCD가 되겠죠.

 

2. 그럼, SCC를 기준으로 생각해보면?

하나의 SCC를 생각해보면, 서로가 서로에게 영향을 끼치는 구조가 됩니다.

서로가 서로에게 영향을 계속해서 끼치다 보면, 동일한 SCC에 들어가는 사람들이 가지게 되는 수는 그 SCC에 있던 수들의 GCD가 되겠죠.

 

3. SCC로 만들어진 DAG에 대해서는?

\( V \)에서 \( W \)로 가는 간선이 있다면,

\( V \)에 있는 사람들 역시 \( W \)에 영향을 줄 수 있다는 의미가 되니,

\( W \)가 가지는 값은 (\( V \)의 GCD와 \( W \)의 GCD)의 GCD로 업데이트할 수 있습니다.

 

4. 최종 값이 \( K \)인 정점의 개수를 세는 방법은?

최종 값이 \( K \)인 SCC들에 대해, 각각의 정점 개수를 다 더해주면 됩니다.

 

5. 코드

ll arr[10020]; ll val[10020];
vector<int> adj[10020];
 
stack<int> stk;
int ord[10020], o;
int scc[10020];
int dfs(int now){
    stk.push(now);
    int res = ord[now] = ++o;
    for (int nxt : adj[now]){
        if (ord[nxt] == 0){ res = min(res, dfs(nxt)); }
        else if (scc[nxt] == 0){ res = min(res, ord[nxt]); }
    }
    if (res == ord[now]){
        while (!stk.empty()){
            int vtx = stk.top(); stk.pop();
            scc[vtx] = now; val[now] = gcd(val[now], arr[vtx]);
            if (vtx == now){ break; }
        }
    }
    return res;
}
 
vector<int> dag[10020]; int cnt[10020];
void Main(){
    int t; cin >> t; while (t--){
        int n, m; ll k; cin >> n >> m >> k;
        while (m--){
            int v, w; cin >> v >> w;
            adj[v].push_back(w);
        }
        for (int i = 1; i <= n; i++){ cin >> arr[i]; val[i] = arr[i]; }
        for (int i = 1; i <= n; i++){
            if (ord[i] == 0){ dfs(i); }
        }
        for (int v = 1; v <= n; v++){
            //cout << "SCC " << v << " = " << scc[v] << endl << flush;
            for (int w : adj[v]){
                if (scc[v] == scc[w]){ continue; }
                dag[scc[v]].push_back(scc[w]); cnt[scc[w]] += 1;
            }
        }
        queue<int> q;
        for (int v = 1; v <= n; v++){
            if (scc[v] == v && cnt[v] == 0){ q.push(v); }
        }
        while (!q.empty()){
            int now = q.front(); q.pop();
            for (int nxt : dag[now]){
                cnt[nxt] -= 1; if (cnt[nxt] == 0){ q.push(nxt); }
                val[nxt] = gcd(val[nxt], val[now]);
            }
        }
        int ans = 0;
        for (int v = 1; v <= n; v++){ ans += (val[scc[v]] == k); }
        cout << ans << endl;
        for (int i = 1; i <= n; i++){
            arr[i] = val[i] = ord[i] = o = scc[i] = 0;
            adj[i].clear(); dag[i].clear();
        }
    }
}