💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 두 정수 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';
	}
}

강한 결합 요소 입문용 문제입니다.
이번 알고리즘유형은 기존에 모르고있던거라서 충분히 이론공부를 한뒤에 진행했습니다.
입문용 문제라 그런지 한번에 맞췄습니다.

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~