社区讨论
样例3,4没过,求助qwq
P8435【模板】点双连通分量参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mhj8ylwy
- 此快照首次捕获于
- 2025/11/03 22:40 4 个月前
- 此快照最后确认于
- 2025/11/03 22:40 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,tot,num,cnt,root;
int ver[(int)4e6+10],nex[(int)4e6+10],head[(int)5e5+10],dfn[(int)5e5+10],low[(int)5e5+10];
bool cut[(int)4e6+10],yzy[(int)5e5+10];
vector < vector<int> > c;
vector <int> pjr(1);
stack <int> dcc;
void add(int x,int y){
ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}
void tarjan(int x) {
dfn[x]=low[n]=++cnt;
dcc.push(x);
int y,z,flag=0;
if(x==root&&head[x]==0){
yzy[x]=true;
pjr[0]=x;
c.push_back(pjr);
num++;
return ;
}
for(int i=head[x];i;i=nex[i]){
y=ver[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1) cut[x]=true;
pjr[0]=x;
c.push_back(pjr);
yzy[x]=true;
num++;
do{
z=dcc.top();
c[num-1].push_back(z);
yzy[z]=true;
dcc.pop();
}while(z!=y);
//c[num-1].push_back(dcc.top());
//yzy[dcc.top()]=true;
//dcc.pop();
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
freopen("in.txt","r",stdin);
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) root=i,tarjan(i);
}
cout<<num+1<<endl;
for(int i=0;i<c.size();i++){
cout<<c[i].size()<<" ";
for(int j=0;j<c[i].size();j++){
cout<<c[i][j]<<" ";
}
cout<<endl;
}
for(int i=1;i<=n;i++) if(!yzy[i]) pjr.push_back(i);
if(pjr.size()>1){
cout<<pjr.size()-1<<" ";
for(int i=1;i<pjr.size();i++) cout<<pjr[i]<<" ";
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...