哇!糖浆!
查看原帖
哇!糖浆!
482730
aSunnyDay楼主2021/4/21 19:47

你萌可以认为我是个btd

大家好,一道tarjan板子题被我咕了3天了没咕出来,还请各位大佬看一下,谢谢!

#include<bits/stdc++.h>
#define N 5009
using namespace std;
typedef long long ll;
ll n,m,low[N],dfn[N],cnt,ins[N],Belong[N],Bcnt=0;
vector<ll> to[N],e[N];
stack<ll> s;
void tarjan(ll x,ll fa){
	low[x]=dfn[x]=++cnt;
	ins[x]=1;
	s.push(x);
	for(ll i=0,v;i<to[x].size();++i)
		if(!dfn[v=to[x][i]]){
			tarjan(v,x);low[x]=min(low[x],low[v]);
		}else if(v!=fa) low[x]=min(low[x],dfn[v]);
	if(dfn[x]==low[x]){
		ll v;
		++Bcnt;
		do{
			v=s.top();
			s.pop();
			Belong[v]=Bcnt;
			ins[v]=0;
		}while(v!=x);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(ll i=1;i<=m;++i){
		ll x,y,v;
		cin>>x>>y>>v;
		to[x].push_back(y);
		if(v==2) to[y].push_back(x);
	}
	tarjan(1,0);
//	for(ll i=1;i<=n;++i) cout<<Belong[i]<<" "<<endl;
	for(ll i=1;i<=n;++i)e[Belong[i]].push_back(i);
	ll ma=0;
	for(ll i=1;i<=n;++i) if(e[i].size()>e[ma].size()) ma=i;
	cout<<e[ma].size()<<endl;
	for(ll i=0;i<e[ma].size()-1;++i) cout<<e[ma][i]<<" ";
	cout<<e[ma][e[ma].size()-1];
	return 0;
}
2021/4/21 19:47
加载中...