QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#44717#999. 边双连通分量Remakee#RE 5ms13200kbC++142.0kb2022-08-21 11:35:432022-08-21 11:35:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-21 11:35:44]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:13200kb
  • [2022-08-21 11:35:43]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool inline chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
	x = 0; int f = 1; char s = getchar();
	while (s > '9' || s < '0') { if (s == '-') f = -1; s = getchar(); }
	while (s <= '9' && s >= '0') x = x * 10 + s - '0', s = getchar();
	x *= f;
}

const int N = 1e5 + 5, M = 5e5 + 5;

int n, m, A[M], B[M], f[N];

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

void inline merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return ;
	f[x] = y;
}

bool st[M];

int head[N], numE = 1;

struct E{
	int next, v;
} e[M << 1];

void add(int u, int v) {
	e[++numE] = (E) { head[u], v };
	head[u] = numE;
}

int dfn[N], low[N], dfncnt;

void tarjan(int u, int la) {
	dfn[u] = low[u] = ++dfncnt;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if ((i ^ 1) == la) continue;
		if (!dfn[v]) {
			tarjan(v, i);
			chkMin(low[u], low[v]);
			if (low[v] > dfn[u]) {
				st[i >> 1] = 1;
			}
		} else chkMin(low[u], dfn[v]);
	}
}

vector<int> b[N];

int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++) f[i] = i;
	for (int i = 1; i <= m; i++) {
		int u, v; read(u), read(v);
		++u, ++v;
		A[i] = u, B[i] = v;
		add(u, v), add(v, u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
	for (int i = 1; i <= m; i++)
		if (!st[i]) merge(A[i], B[i]);
	for (int i = 1; i <= n; i++) b[find(i)].pb(i);
	int ct = 0;
	for (int i = 1; i <= n; i++) {
		if (find(i) == i) ct++;
	}
	cout << ct << endl;
	for (int i = 1; i <= n; i++) {
		if (find(i) == i) {
			cout << b[i].size() << " ";
			for (int v: b[i]) cout << v - 1 << " ";
			cout << endl;
		}
	}
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 13200kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 0 1 2 3 

result:

ok OK

Test #2:

score: 0
Accepted
time: 1ms
memory: 11916kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 0 1 4 5 9 11 
4 2 3 10 12 
3 6 7 8 

result:

ok OK

Test #3:

score: 0
Accepted
time: 4ms
memory: 12220kb

input:

2 2
0 1
1 0

output:

1
2 0 1 

result:

ok OK

Test #4:

score: -100
Runtime Error

input:

200000 200000
127668 148778
77100 11865
85144 199231
39485 84917
102044 187263
130204 174776
26220 198288
162188 12078
92196 146334
120537 38083
150353 160479
18707 6545
101149 25450
62271 9177
38892 6454
11709 191939
89247 145109
140599 121858
197410 148980
55975 169098
128576 59852
68224 182347
89...

output:


result: