TARJAN割点模板求查错!
查看原帖
TARJAN割点模板求查错!
567739
Sellaris楼主2022/2/8 01:29

rt,割点板子求大佬看。kl

///*****Sellaris*****///
//#pragma GCC optimize(2)
//#pragma once
#define _USE_MINGW_ANSI_STDIO 1
#include <bits/stdc++.h>//<bits/extc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define modulu 2147483647 //998844353 
using namespace std; 
using namespace __gnu_pbds;
typedef long double ldouble;
typedef pair<int,int> pii;
tree <ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> TREE ;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f; //x=(x<<1)+(x<<3)+(ch^48);
}
void write(register int x){
    if(x<0){putchar('-'),x=-x;}
    if(x>9){write(x/10);}putchar(x%10+'0');
	return;
}
const int N=2e6;
struct Edge{int to,next;}G[N<<1];
int head[N],tot=0; 
int n,m;
int dfn[N],low[N],cut[N];//最早时间,自己时间,标记 
ll cnt=0;
ll ans=0;
void add(int x,int y) {
	G[++tot].to=y;
	G[tot].next=head[x];
	head[x]=tot;
}
void tarjan(int u,int fa){
	low[u]=++cnt;
	dfn[u]=low[u];
	int child=0;
	for(int i=head[u];i;i=G[i].next){
		int v=G[i].to;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u] && u!=fa) cut[u]=1;
			if(u==fa) child++;
		}
		dfn[u]=min(dfn[u],low[v]);
	}
	if(u==fa && child>=2) cut[u]=1;
	return;
}
signed main(){ /*int32_t*/
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); std::cout.tie(NULL);
	//freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(head,0,sizeof(head));
	n=read(),m=read();
	for(int i=1;i<=m;i++) {int a=read(),b=read();add(a,b);add(b,a);}
	for(int i=1;i<=n;i++)
		if(dfn[i]==0) tarjan(i,i);
	for(int i=1;i<=n;i++) if(cut[i]) ans++;
	write(ans),puts("");
	for(int i=1;i<=n;i++) if(cut[i]) write(i),putchar(' ');
	return 0;
}


2022/2/8 01:29
加载中...