测试点本地过了但线上RE
查看原帖
测试点本地过了但线上RE
388602
CA_FZZSL楼主2024/10/24 14:33
#include<bits/stdc++.h>
#define MAXN 20010
#define MAXM 100010
#define int long long
using namespace std;

inline void read(int &a){
	bool w = false; a = 0;
	char c = getchar();
	while(c<'0'||c>'9'){if(c='-')w=true;c=getchar();}
	while(c>='0'&&c<='9'){a=(a<<3)+(a<<1)+(c^48);c=getchar();}
	if(w) a = -a;
}

int n,m;
int h[MAXN],ei=0;
struct Node{
	int to;
	int nxt;
}e[MAXM*2];

void add(int x,int y){
	ei++;
	e[ei].to = y;
	e[ei].nxt = h[x];
	h[x] = ei;
}

void swap(int &a,int &b){
	int z = a;
	a = b;
	b = z;
}

int heap[MAXN],hcnt = 0;
void push(int x){
	heap[++hcnt] = x;
	int now = hcnt;
	while(now>1 && heap[now>>1]>heap[now]){
		swap(heap[now],heap[now>>1]);
		now >>= 1;
	}
}
int top(){
	return heap[1];
}
void pop(){
	heap[1] = heap[hcnt--];
	int now = 1;
	while((now<<1)<=hcnt && heap[now]>heap[now<<1]
	|| (now<<1|1)<=hcnt && heap[now]>heap[now<<1|1]){
		if(now<<1|1<=hcnt && heap[now<<1|1]<heap[now<<1]){
			swap(heap[now],heap[now<<1|1]);
			now = now<<1|1;
			continue;
		}
		swap(heap[now],heap[now<<1]);
		now <<= 1;
	}
}

int gd=0,gb=0;
bool fl[MAXN];
int dfn[MAXN],low[MAXN],dfsn=0;
void tarjan(int x,int f){
	int child = 0;
	dfn[x] = low[x] = ++dfsn;
	for(int i=h[x]; i; i=e[i].nxt){
		int to = e[i].to;
		if(!dfn[to]){
			child++;
			tarjan(to,x);
			low[x] = min(low[to],low[x]);
			if(low[to]>=dfn[x] && !fl[x] && x!=f){
				fl[x] = true; gd++;
				push(x);
			}
			if(low[to]>dfn[x]) gb++;
		}else{
			low[x] = min(low[x],dfn[to]);
		}
	}
	if(x == f && child>=2 && !fl[x]){
		fl[x] = true;
		gd++;
	}
}

void dotarjan(){
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,i);
	}
}

signed main(){
	
	read(n);
	read(m);
	int x,y;
	for(int i=1;i<=m;i++){
		read(x);
		read(y);
		add(x,y);
		add(y,x);
	}
	
	dotarjan();
	printf("%lld\n",gd);
	while(hcnt){
		printf("%lld ",top());
		pop();
	}
	
	return 0;
}
2024/10/24 14:33
加载中...