QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92330#906. 强连通分量zhaohaikun#RE 3ms14708kbC++141.4kb2023-03-30 15:56:522023-03-30 15:56:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 15:56:54]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:14708kb
  • [2023-03-30 15:56:52]
  • 提交

answer

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 2e5 + 10;
int n, m, dfn[N], low[N], sccnum[N], scccnt, dfscnt, sta[N], stacnt;
vector <int> v[N], p[N];
void dfs(int x) {
	low[x] = dfn[x] = ++dfscnt;
	sta[stacnt++] = x;
	for (int i: v[x])
		if (!dfn[i]) {
			dfs(i);
			chkmin(low[x], low[i]);
		} else if (!sccnum[i]) {
			chkmin(low[x], dfn[i]);
		}
	if (low[x] == dfn[x]) {
		scccnt++;
		do {
			sccnum[sta[--stacnt]] = scccnt;
			p[scccnt].push_back(sta[stacnt]);
		} while (sta[stacnt] != x);
	}
}
signed main() {
	read(n); read(m);
	F(i, 1, m) {
		int x, y; read(x); read(y);
		x++; y++;
		v[x].push_back(y);
	}
	F(i, 1, n)
		if (!dfn[i]) dfs(i);
	cout << scccnt << endl;
	DF(i, scccnt, 1) {
		cout << p[i].size() << " ";
		for (int j: p[i]) cout << j - 1 << " "; cout << endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14708kb

input:

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

output:

4
1 5 
2 4 1 
1 2 
2 3 0 

result:

ok OK

Test #2:

score: -100
Runtime Error

input:

500000 500000
389812 410922
255712 339244
274009 248522
347288 199231
235313 301629
469588 84917
364188 449407
392348 436920
26220 198288
162188 468965
274222 92196
463222 408478
231663 467768
382681 38083
412497 160479
280851 268689
101149 25450
62271 9177
38892 268598
273853 250782
191939 89247
40...

output:


result: