Archy_ @ 2024-07-10 11:05:45
看了一些,我输出的边双连通分量个数大于正解,是不是哪里的判定条件少了,我看了好久,求助!!!
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#define N 500010
#define M 2000010
using namespace std;
int n, m, low[N], dfn[N], dfncnt, bcccnt;
bool vis[N];
vector <int> g[N],ans[N];
map <pair<int,int>,bool> mp;
inline int rd() {
int w = 1, x = 0;
char c = getchar();
while(c < 48 || c > 57) {
if(c == 45) w *= -1;
c = getchar();
}
while(c >= 48 && c<= 57) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * w;
}
void tarjan(int u, int fa){
dfn[u] = low[u] = ++dfncnt;
for(int &v : g[u]){
if(!dfn[v]){
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]){
mp[pair<int, int>(u, v)] = 1;
mp[pair<int, int>(v, u)] = 1;
}
}
else if(v != fa)low[u] = min(low[u], dfn[v]);
}
}
void dfs(int u,int id){
vis[u] = 1;
ans[bcccnt].push_back(u);
for(auto &v : g[u]){
if(mp[pair<int, int>(u, v)] || vis[v]) continue;
if(!vis[v]) dfs(v, id);
}
}
int main() {
n = rd(), m = rd();
for(int i = 1;i <= m;i ++) {
int u = rd(), v = rd();
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1;i <= n;i ++)
if (!dfn[i])
tarjan(i, i);
for(int i = 1;i <= n;i ++)
if(!vis[i])
dfs(i,++bcccnt);
printf("%d\n",bcccnt);
for(int i = 1;i <= bcccnt;i ++) {
printf("%d ",ans[i].size());
for(int &j : ans[i])
printf("%d ",j);
printf("\n");
}
return 0;
}
by Archy_ @ 2024-07-10 11:06:43
mp是边与bool的映射,判断bridge的
by hao_zi6366 @ 2024-08-01 20:39:59
有重边的可能性,当一条边被多次输入时,这条边不可能是桥。