Lyy450605 @ 2023-08-10 22:00:52
求调试,最后两个点
#include <bits/stdc++.h>
#define Lon long long
using namespace std;
const int N=1e6+10;
const int M=2e6+10;
const int INF=0x3f3f3f3f;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct LINK{//结构体
struct Node{
int to;
int next;
};
Node edge[M<<1]; int head[N],cnt;
LINK (){//构造函数
cnt=1;//用异或
}
inline void Insert(int from,int to){
++cnt;
edge[cnt].to=to;
edge[cnt].next=head[from]; head[from]=cnt;
}
};
int n,m,a,b; LINK G;
int low[N],dfn[N],dfcnt; bitset<M> vis1; bitset<N> vis2;
vector<int> ans[N]; int dcc;
void tarjen(int cur,int last){
dfn[cur]=low[cur]=++dfcnt;
for(int i=G.head[cur];i;i=G.edge[i].next){
int to=G.edge[i].to;
if(to==last) continue;//
if(!dfn[to]){
tarjen(to,cur);
low[cur]=min(low[cur],low[to]);
if(low[to]>dfn[cur]){//
vis1[i]=1;
vis1[i^1]=1;
}
}
else low[cur]=min(low[cur],dfn[to]);
}
}
void dfs(int cur,int last){
vis2[cur]=1;
ans[dcc].push_back(cur);
for(int i=G.head[cur];i;i=G.edge[i].next){
int to=G.edge[i].to;
if(vis2[to]||vis1[i]) continue;
dfs(to,cur);
}
}
signed main(){//想法:删除桥
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b;
if(a==b) continue;
G.Insert(a,b);
G.Insert(b,a);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjen(i,0);
}
}
for(int i=1;i<=n;i++){
if(!vis2[i]){
dcc++;
dfs(i,0);
}
}
cout<<dcc<<"\n";
for(int i=1;i<=dcc;i++){
cout<<ans[i].size()<<" ";
for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
cout<<"\n";
}
return 0;
}
by Lyy450605 @ 2023-08-11 08:23:06
捞,求调试qwq
by Lyy450605 @ 2023-08-11 08:34:19
???
我把空间开到
const int N=2e6+10;
const int M=4e6+10;
然后过了
by wangyang0222 @ 2023-08-11 14:13:50
%%%
by Nwayy @ 2023-08-26 10:16:03
@Lyy450605 因为你要存双向边,空间必须开到两倍。