社区讨论

割点板子求助,找不出问题了

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...