你萌可以认为我是个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;
}