QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1267 | #792613 | #999. 边双连通分量 | RDFZchenyy | oyzr | Failed. | 2024-11-29 12:00:34 | 2024-11-29 12:00:36 |
詳細信息
Extra Test:
Accepted
time: 1ms
memory: 5652kb
input:
2 3 0 0 0 1 1 1
output:
2 1 1 1 0
result:
ok OK
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#792613 | #999. 边双连通分量 | oyzr | AC ✓ | 46ms | 20764kb | C++23 | 1.9kb | 2024-11-29 11:58:50 | 2024-11-29 11:58:50 |
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXM = 2e5 + 5;
int read(){
int res = 0, flag = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
flag = -1;
for (; c >= '0' && c <= '9'; c = getchar())
res = (res << 1) + (res << 3) + (c ^ 48);
return res * flag;
}
class Graph{
private:
const static int MAXNODE = MAXN, MAXEDGE = MAXM * 2;
struct Edge{
int v, next;
};
int tot = 1;
public:
Edge t[MAXEDGE];
int h[MAXNODE];
void addEdge(int u, int v){
++tot;
t[tot].v = v;
t[tot].next = h[u];
h[u] = tot;
}
}G;
int dfn[MAXN], low[MAXN], cnt = 0;
int eccId[MAXN], eccCnt = 0;
vector <int> ecc[MAXN];
stack <int> s;
void tarjan(int u, int from){
low[u] = dfn[u] = ++cnt;
s.push(u);
for (int i = G.h[u]; i; i = G.t[i].next){
if (i == (from ^ 1))
continue;
int v = G.t[i].v;
if (!dfn[v]){
tarjan(v, i);
low[u] = min(low[u], low[v]);
}else
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]){
++eccCnt;
int v;
do {
v = s.top();
s.pop();
eccId[v] = eccCnt;
ecc[eccCnt].push_back(v);
}while (v != u);
}
}
int main(){
int n = read(), m = read();
for (int i = 1; i <= m; i++){
int u = read(), v = read();
u++, v++;
G.addEdge(u, v);
G.addEdge(v, u);
}
for (int i = 1; i <= n; i++)
if (!eccId[i])
tarjan(i, 0);
cout << eccCnt << '\n';
for (int i = 1; i <= eccCnt; i++){
cout << ecc[i].size() << ' ';
for (auto x: ecc[i])
cout << x - 1 << ' ';
cout << '\n';
}
return 0;
}