社区讨论
割点板子求助,找不出问题了
学术版参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo7yd9bn
- 此快照首次捕获于
- 2023/10/27 09:46 2 年前
- 此快照最后确认于
- 2023/10/27 09:46 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
struct Edge{
int u,v,next;
}a[N];
int head[N],low[N],dfn[N],root,flag;
int tot=1,num;
int cnt;
bool cut[N];
void add(int u,int v)
{
a[++tot].u=u;
a[tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void tarjan(int x,int in_edge)
{
dfn[x]=low[x]=++num;
flag=0;
for(int i=head[x];i;i=a[i].next){
int y=a[i].v;
if(!dfn[y]){
tarjan(y,i);
low[x]=min(low[y],low[x]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root){
cut[x]=1;
}
else if(flag>1) cut[x]=1;
}
}
else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
}
}
int main()
{
// freopen("P3388_1.in","r",stdin);
// freopen("P3388_1.txt","w",stdout);
memset(head,0,sizeof(head));
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x==y) continue;
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) root=i,tarjan(i,0);
}
for(int i=1;i<=n;i++){
if(cut[i]) cnt++;
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(cut[i]) cout<<i<<' ';
}
return 0;
}
dalao的AC代码
CPP#include<iostream>
using namespace std;
typedef long long ll;
const int N=100010,M=500010;
int head[N],ver[M*2],Next[M*2];
int low[N],dfn[N],tot,num,n,m,ss,root;
bool cut[N];
void add(int x,int y){
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
int flag=0;
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[y],low[x]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1) cut[x]=true;
}
}
else
low[x]=min(low[x],dfn[y]);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
tot=1;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x==y) continue;
add(x,y);add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) root=i,tarjan(i);
for(int i=1;i<=n;i++)
if(cut[i]) ss++;
cout<<ss<<'\n';
for(int i=1;i<=n;i++)
if(cut[i]) cout<<i<<' ';
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...