社区讨论
why 48pts?
P8435【模板】点双连通分量参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhk2jrk0
- 此快照首次捕获于
- 2025/11/04 12:28 4 个月前
- 此快照最后确认于
- 2025/11/04 12:28 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=500010,M=2000010;
vector<int> g[N];
int tot,dfn[N],low[N],root,cnt;
bool cut[N];
stack<int>s;
vector<int> res[N];
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
s.push(x);
int i,j,y,child=0,z;
if(g[x].size()==0)
{
res[++cnt].push_back(x);
}
for(i=0;i<g[x].size();i++)
{
y=g[x][i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
child++;
if(child>=2||x!=root) cut[x]=1;
cnt++;
while(1)
{
z=s.top();
s.pop();
res[cnt].push_back(z);
if(z==y) break;
}
}
res[cnt].push_back(x);
}
else low[x]=min(low[x],dfn[y]);
}
}
int main()
{
int n,m,i,j,u,v;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
if(u==v) continue;
g[u].push_back(v);
g[v].push_back(u);
}
for(i=1;i<=n;i++)
if(!dfn[i])
{
while(s.size()) s.pop();
root=i;
tarjan(i);
}
printf("%d\n",cnt);
for(i=1;i<=cnt;i++)
{
printf("%d ",res[i].size());
for(j=0;j<res[i].size();j++)
printf("%d ",res[i][j]);
printf("\n");
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...