🧺입력
첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.
정점은 1부터 V까지 번호가 매겨져 있다.
🧺출력
첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.
🔮예제 입력1
7 9 1 4 4 5 5 1 1 6 6 7 2 7 7 3 3 7 7 2
🔮예제 출력1
3 1 4 5 -1 2 3 7 -1 6 -1
그래프 이론, 강한 결합 요소
플래티넘V
그냥 일반적인 강한 결합 요소 문제입니다.
1부터 V까지 갱신이 안된 수를 dfs돌려줬습니다.
그다음 오름차순 정렬한다음에 출력해줬습니다.
#include <bits/stdc++.h>
constexpr int MAX = 10001;
constexpr int INF = 987654321;
std::stack<int> s;
std::vector<std::vector<int>> scc;
std::vector<int> adj[MAX];
int id = 0, d[MAX];
bool visit[MAX];
int dfs(int x) {
d[x] = ++id;
s.push(x);
int parent = d[x];
for (std::size_t i = 0; i < adj[x].size(); ++i) {
int y = adj[x][i];
if (d[y] == 0) parent = std::min(parent, dfs(y));
else if (!visit[y]) parent = std::min(parent, d[y]);
}
if (parent == d[x]) {
std::vector<int> tmp;
while (!s.empty()) {
int t = s.top();
s.pop();
tmp.push_back(t);
visit[t] = true;
if (t == x) break;
}
scc.push_back(tmp);
}
return parent;
}
int main() {
int V, E;
std::cin >> V >> E;
for (int i = 0; i < E; ++i) {
int a, b;
std::cin >> a >> b;
adj[a].push_back(b);
}
for (int i = 1; i <= V; ++i) if (d[i] == 0) dfs(i);
std::cout << scc.size() << '\n';
for (int i = 0; i < scc.size(); ++i) std::sort(scc[i].begin(), scc[i].end());
std::sort(scc.begin(), scc.end());
for (int i = 0; i < scc.size(); ++i) {
for (int j = 0; j < scc[i].size(); ++j) {
std::cout << scc[i][j] << ' ';
}
std::cout << -1 << '\n';
}
}
강한 결합 요소 입문용 문제입니다.
이번 알고리즘유형은 기존에 모르고있던거라서 충분히 이론공부를 한뒤에 진행했습니다.
입문용 문제라 그런지 한번에 맞췄습니다.
궁금한 부분있으시면 댓글로 질문주세요~