February 09, 2021
강한 연결 요소(SCC), 플로이드 와셜
도시 i 에 세운 경찰서가 도시 j 를 통제할 수 있으려면, i 에서 j 로 갔다가, 다시 돌아오는 경로가 존재해야 한다.
유향 그래프에서 정점 u 와 v 에 대해 서로 갈 수 있는 경로가 있다면 강하게 연결되었다고 할 수 있다. 강한 연결 요소 알고리즘으로 DFS 기반 선형 시간 알고리즘인 코사라주 알고리즘을 사용했다.
코사라주 알고리즘은 SCC 분리 알고리즘으로 역방향 그래프가 원래 그래프와 정확히 같은 SCC를 갖는다는 사실을 이용한다.
시간 복잡도는 인접 리스트인 경우 , 인접 행렬인 경우 이다.
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX = 100;
int cost[MAX];
bool visited[MAX];
vector<int> graph[MAX];
vector<int> reverse_graph[MAX];
stack<int> st;
void visit(int u) {
visited[u] = true;
for (auto adj : graph[u])
if (!visited[adj]) visit(adj);
st.push(u);
}
int assign(int u) {
int ret = cost[u];
visited[u] = true;
for (auto adj : reverse_graph[u])
if (!visited[adj]) ret = min(ret, assign(adj));
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> cost[i];
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < n; j++) {
if (s[j] == '1') {
graph[i].push_back(j);
reverse_graph[j].push_back(i);
}
}
}
for (int i = 0; i < n; i++)
if (!visited[i]) visit(i);
memset(visited, false, sizeof(visited));
while (!st.empty()) {
int u = st.top();
st.pop();
if (!visited[u]) ans += assign(u);
}
cout << ans << endl;
return 0;
}
정점의 수가 100이기 때문에 플로이드 와셜 알고리즘으로도 풀 수 있다. 모든 정점에 대해 갈 수 있는 모든 루트를 표시하고, 되돌아올 수 있는지 확인하면 된다.
시간 복잡도는 이다.
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100;
int cost[MAX];
bool route[MAX][MAX];
bool visited[MAX];
int dfs(int u, int n) {
int ret = cost[u];
visited[u] = true;
for (int i = 0; i < n; i++)
if (!visited[i] && route[u][i] && route[i][u])
ret = min(ret, dfs(i, n));
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, ans = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> cost[i];
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < n; j++)
if (s[j] == '1') route[i][j] = 1;
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (route[i][k] && route[k][j]) route[i][j] = 1;
for (int i = 0; i < n; i++)
if (!visited[i]) ans += dfs(i, n);
cout << ans << endl;
return 0;
}