社区讨论
vector建图如何去重边?
P2860[USACO06JAN] Redundant Paths G参与者 7已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mhjl0f3m
- 此快照首次捕获于
- 2025/11/04 04:17 4 个月前
- 此快照最后确认于
- 2025/11/04 04:17 4 个月前
Rt.
CPP#include<bits/stdc++.h>
using namespace std;
const int N=500005,M=4000005;
int n,m,dfncnt,dfn[N],low[N],inst[N],st[M],stot,root,bcccnt;
vector<int>R[N];
vector<int>bcc[N];
void tarjan(int u)
{
dfn[u]=low[u]=++dfncnt,
st[++stot]=u,inst[u]=1;
if(u==root&&(!R[u].size()))
{
bcc[++bcccnt].push_back(u);
return ;
}
for(auto v:R[u])
{
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
++bcccnt;
while(st[stot+1]!=v)
bcc[bcccnt].push_back(st[stot--]);
bcc[bcccnt].push_back(u);
}
}else if(inst[v]&&)
low[u]=min(low[u],dfn[v]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x==y) continue;
R[x].push_back(y);
R[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) root=i,tarjan(i);
printf("%d\n",bcccnt);
for(int i=1;i<=bcccnt;i++)
{
printf("%d ",bcc[i].size());
for(auto v:bcc[i])
printf("%d ",v);
printf("\n");
}
return 0;
}
91分
回复
共 9 条回复,欢迎继续交流。
正在加载回复...