链式前向星,为什么加上去重边就错了
查看原帖
链式前向星,为什么加上去重边就错了
577581
00000110hh楼主2022/5/20 06:33
#include<bits/stdc++.h>
using namespace std;
int n,m;
int x,y; 
int fa[20005];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int u,int v){
	fa[find(u)]=fa[find(v)];
	return;
}
struct node{
	int v;
	int nex;
	bool vis;
}e[200005];
int head[20005];
int cnt;
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].nex=head[u];
	head[u]=cnt;
	e[++cnt].v=u;
	e[cnt].nex=head[v];
	head[v]=cnt;
	merge(u,v);
	return;
}
int dfn[20005],low[20005];
bool key[20005];//记录割点
int num;
int anu;
int child;
int color[200005]; 
void dfs(int u){//目的:点u是否是割点
	//算法公设:基于对图dfs的生成树 
	//路径:树顶看出度,其余看子节点的回边
	//可见,判定与其子节点(出度&dfn的传递)有关,继而与祖先(dfn的传递)有关 
	//操作:记录dfn(伴随dfs),传递dfn(借助图边,只与祖先有关,本层递归中递归之前),比较dfn(本层递归中递归之后)
	//思想启发:对图dfs的方法(A处)及伴生性质(已搜到为回边及dfn一对一映射带来判定的便利性) 
	dfn[u]=++num;
	low[u]=dfn[u];
	for(int i=head[u];i;i=e[i].nex){//A 
		int v=e[i].v;
		if(!dfn[v]){//A
			if(dfn[u]==1) child++;
			dfs(v);
            low[u]=min(low[v],low[u]);
			if(low[v]>=dfn[u]&&dfn[u]>1){//勿忘 
				if(!key[u]){
					anu++;
					key[u]=1;
				}
			}
		}
		else if(!color[i^1]){//是祖先 
			low[u]=min(low[u],dfn[v]);
		}
		color[i]=1;
	} 
	if(dfn[u]==1&&child>=2){
		anu++;
        key[u]=1;
	}
	return;
}
int main(){
	std::ios::sync_with_stdio();
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			dfs(i);
			num=0;
			child=0;
		}
	}
	cout<<anu<<endl;
	for(int i=1;i<=n;i++){
        if(key[i]) cout<<i<<" ";
    }
	return 0;
}
2022/5/20 06:33
加载中...