QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#411619#906. 强连通分量ieeWA 0ms3576kbC++171.1kb2024-05-15 16:42:212024-05-15 16:42:21

Judging History

你现在查看的是最新测评结果

  • [2024-05-15 16:42:21]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3576kb
  • [2024-05-15 16:42:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> e(n), g(n);
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		e[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int> ord, vis(n);
	function<void(int)> dfs = [&](int u) {
		if (vis[u]) return;
		vis[u] = 1;
		for (int v : e[u]) {
			dfs(v);
		}
		ord.push_back(u);
	};
	for (int i = 0; i < n; i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	reverse(ord.begin(), ord.end());
	vis.assign(n, 0);
	vector<int> col(n);
	vector<vector<int>> nodes(n);
	int rt, tot = 0;
	function<void(int)> dfs1 = [&](int u) {
		if (vis[u]) return;
		vis[u] = 1;
		col[u] = rt;
		nodes[rt].push_back(u);
		for (int v : g[u]) {
			dfs1(v);
		}
	};
	for (int i : ord) {
		if (!vis[i]) rt = i, dfs1(i), tot++;
	}
	cout << tot << "\n";
	vector<int> out(n);
	for (int i = 0; i < n; i++) {
		if (out[col[i]]) continue;
		out[col[i]] = 1;
		sort(nodes[col[i]].begin(), nodes[col[i]].end());
		cout << nodes[col[i]].size();
		for (int x : nodes[col[i]]) {
			cout << " " << x;
		}
		cout << "\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3576kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
2 0 3
2 1 4
1 2
1 5

result:

wrong answer 5 is later than 2, but there is an edge (5, 2)