[BOJ] 2150 : Strongly Connected Component

15509 ワード
boj C きょうけつごうげんそ アルゴリズム#アルゴリズム# scc テキストリンク

💉質問内容


問題に答える

💉にゅうしゅつりょく


🧺入力
第1行は2つの整数V(1≦V≦10000),E(1≦E≦100000)を与える.これは,図形がV個の頂点とE本の幹線からなることを意味する.次のE行は、幹線に関する情報を表す2つの整数A,Bを与える.これは、A番頂点とB番頂点が接続されていることを意味します.このとき方向はA→Bです.
頂点は1～Vで番号付けされます.
🧺しゅつりょく
1行目はSCCの個数Kを出力する.次のK行は、行ごとに1つのSCCに属する頂点の番号を出力します.各行末尾出力−1は、その行の末尾を示す.各SCCが出力されると、頂点は昇順に出力されます.また、複数のSCCについては、その中の最小頂点の頂点番号で出力される.

🔋サンプルI/O


🔮入力例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';
	}
}
強結合要素の入門問題.
今回のアルゴリズムタイプは以前は知らなかったので,理論を十分に学習した上で行った.
入門問題かもしれないのですぐさま正解しました

💉終了時..。


気になる部分があればコメントで質問しましょう~
ブートストラップによるDjangoメッセージ設定
JavaScriptの[無効]からライブラリを書く