QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#44717 | #999. 边双连通分量 | Remakee# | RE | 5ms | 13200kb | C++14 | 2.0kb | 2022-08-21 11:35:43 | 2022-08-21 11:35:44 |
Judging History
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...