Tarjan板子求调
查看原帖
Tarjan板子求调
648705
Glax712124楼主2024/9/13 19:57

RT,我太弱了。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,ans,u[200005],v[200005],first[20005],nxt[200005],num[20005],low[20005];
bool book[20005];
void tarjan(int x,int father){
	int child=0;
	cnt++;
	num[x]=low[x]=cnt;
	for(int i=first[x];nxt[i]!=-1;i=nxt[i]){
		if(num[v[i]]==0){
			child++;
			tarjan(v[i],x);
			low[x]=min(low[x],low[v[i]]);
			if(x!=1&&low[v[i]]>=num[x]){
				book[x]=true;
			}
			else if(x==1&&child==2){
				book[x]=true;
			}
		}
		else if(v[i]!=father){
			low[x]=min(low[x],num[v[i]]);
		}
	}
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		first[i]=-1;
	}
	for(int i=1;i<=2*m;i++){
		cin>>u[i]>>v[i];
		nxt[i]=first[u[i]];
		first[u[i]]=i;
		u[i+1]=v[i];
		v[i+1]=u[i];
		i++;
		nxt[i]=first[u[i]];
		first[u[i]]=i;
	}
	tarjan(1,1);
	for(int i=1;i<=n;i++){
		if(book[i]==true){
			cout<<i<<endl;
		}
	}
	return 0;
}
2024/9/13 19:57
加载中...