1506번 경찰서

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

코테 코딩 필수 추천 복습 면접 scc

강한 연결 요소 scc

복습해야겠다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 101
 
int id, n, cost[Max], p[Max];;
vector<int> v[Max];
bool visit[Max], stop;
 
vector<vector<int> > scc;
stack<int> s;
 
int dfs(int now)
{
    p[now] = ++id;
 
    s.push(now);
 
    int parent = p[now];
 
    for (auto i : v[now])
    {
        int next = i;
 
        if (p[next] == 0) parent = min(parent, dfs(next));
        else if (!visit[next]) parent = min(parent, p[next]);
    }
 
    if (parent == p[now])
    {
        vector<int> SCC;
 
        while (1)
        {
            int t = s.top();
 
            s.pop();
 
            visit[t] = true;
 
            SCC.push_back(t);
 
            if (t == now) break;
        }
 
        sort(SCC.begin(), SCC.end());
 
        scc.push_back(SCC);
    }
 
    return parent;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cost[i]);
    }
 
    for (int i = 1; i <= n; i++) {
        int input;
        for (int j = 1; j <= n; j++) {
            scanf("%1d", &input);
            if (input) {
                v[i].push_back(j);
            }
        }
    }
 
    vector<vector<int> > vt;
    for (int i = 1; i <= n; i++) {
        if (!visit[i]) {
            dfs(i);
        }
    }
 
    int ans = 0;
 
    for (auto i : scc) {
        int Min = 1e9;
        for (auto j : i) {
            Min = min(Min, cost[j]);
        }
        ans += Min;
    }
 
    printf("%d\n", ans);
 
    return 0;
}