为甚这份代码把样例中的4号点也算做了割点
查看原帖
为甚这份代码把样例中的4号点也算做了割点
1268524
DX3906_ourstar楼主2024/11/2 17:12

rt,不理解

#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#define INF 0x7fffffff
using namespace std;
namespace OIfast{//快读快写 
	#define re register
	inline int read(){re char c = getchar();re int n = 0,f = 1;while(c < '0' || c > '9'){if(c == '-'){f = -1;}c = getchar();}while(c >= '0' && c <= '9'){n = n * 10 + c - '0';c = getchar();}return n * f;}inline void print(re int n){if(n < 0){n = -n;putchar('-');}if(n >= 10){print(n / 10);}putchar(n % 10 + '0');return ;}inline void write(re int n,re char c){print(n);putchar(c);return ;}};
using namespace OIfast;

const int N = 1e6 + 5;

int cnt,tot,ans,root,n,m;//ans是割点个数 
int head[N],dfn[N],low[N];
bool vis[N];//标记是否计入了答案 

stack<int> s;
priority_queue<int,vector<int>,greater<int> > q;//小根堆,节点顺序由小到大 

struct edge{
	int v,next;
}e[N];

inline void add(int u,int v){
	cnt ++;
	e[cnt].v = v;
	e[cnt].next = head[u];
	head[u] = cnt;
	return ;
}

inline void Tarjan(int u){
	dfn[u] = low[u] = ++ tot;
	int son = 0;
	for(re int i = head[u];i != -1;i = e[i].next){
		int v = e[i].v;
		if(! dfn[v]){
			son ++;
			Tarjan(v);
			low[u] = min(low[u],low[v]);
			if((low[v] >= dfn[u]) && (u != root)){
				if(! vis[u]){
					ans ++;
					q.push(u);//是割点,入队 
					vis[u] = true;
				}
			}else{
				low[u] = min(low[u],dfn[v]);
			}
		}
	}
	if(son >= 2 && u == root){
		if(! vis[u]){
			ans ++;
			q.push(u);
			vis[u] = true;
		}
	}
	return ;
}

inline void init(){
	memset(head,-1,sizeof(head));
	return ;
}

inline void input(){
	n = read(),m = read();
	for(re int i = 1;i <= m;i ++){
		int u = read(),v = read();
		add(u,v);
		add(v,u);
	}
	return ;
}

inline void solve(){
	for(re int i = 1;i <= n;i ++){
		if(! dfn[i]){
			root = i;
			Tarjan(i);
		}
	}
	return ;
}

inline void output(){
	write(ans,'\n');
	while(! q.empty()){
		write(q.top(),' ');
		q.pop();
	}
	puts("");
	return ;
}

signed main(){
	init();
	input();
	solve();
	output();
	return 0;
}
2024/11/2 17:12
加载中...