92pts,有关根节点的割点
查看原帖
92pts,有关根节点的割点
542881
日常放水WT双奔楼主2022/11/16 23:30

#11有误

估计是根节点的割点判断有误

但是将注释部分写进代码则会0分,不知道哪来的2号割点

没有用栈之类的方法,代码从割边改编而来

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=2e4,maxm=1e5;

struct Edge{
    int u, v, w;//起点,终点,权值
    int nxt = -1;
}
edge[2*maxm + 10];
int head[maxn + 10], cnt = 0;
void init()//初始化链式前向星
{
    cnt=0;
    memset(head, -1, sizeof(head));
    return ;
}
void add_edge(int frm, int to, int val)
{
    edge[++cnt].u = frm;
    edge[cnt].v = to;
    edge[cnt].w = val;
    edge[cnt].nxt = head[frm];
    head[frm] = cnt;
    return ;
}

int res=0;
int dfn[maxn+10],low[maxn+10];
int num=0;
bool cut[maxn+10];
void tarjan(int x,int fa){
	dfn[x]=low[x]=++num;
	if(fa==-1&&head[x]==-1){
		cut[x]=1,res++;
	}
	for(int i=head[x];~i;i=edge[i].nxt){
		int y=edge[i].v;
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y])
				if(!cut[x])//防止重复 
					cut[x]=1,res++;
		}
		else if(edge[i].v!=fa){
			low[x]=min(low[x],dfn[y]);
		}
	}
	return;
}

int n,m;
int main(){
	init();
	memset(cut,0,sizeof cut);
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	scanf("%d%d",&n,&m);
	_for(i,1,m){
		int frm,to;
		scanf("%d%d",&frm,&to);
		add_edge(frm,to,1);add_edge(to,frm,1);
	}
	_for(i,1,n)if(!dfn[i]){
		tarjan(i,-1);
		cut[i]=0,res--;//特别地:非孤独根节点不是割点
//		//除非有两个相邻的y,使得dfn[rot]<=low[y]; 
//		int tot=0;
//		for(int j=head[i];~j;j=edge[j].nxt)if(dfn[i]<=low[edge[j].v])tot++;
//		if(tot>=2)cut[i]=1,res++;
	}
	
    printf("%d\n",res);
	_for(i,1,n) if(cut[i])printf("%d ",i);
	puts("");
	fclose(stdin);
	return 0;
}
2022/11/16 23:30
加载中...