【洛谷】【tarjan】上白泽慧音

题目链接:https://www.luogu.org/problemnew/show/P1726

思路:tarjan强连通分量

按照题意连边,跑一遍tarjan,vector存储,打擂法找最大值

上代码↓

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int MAXN=5005;

int n,m,np,x,y,z,maxn,ans;
int h[MAXN],tp[MAXN],lw[MAXN],clr[MAXN],stk[MAXN];
bool vis[MAXN];
struct rpg{
    int li,nx;
}a[MAXN*10];
vector<int> v[MAXN];

void add(int ls,int nx)
{
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        if(z==1) add(x,y);
        else add(x,y),add(y,x);
    }return;
}

void tarjan(int x)
{
    lw[x]=tp[x]=++tp[0];
    vis[x]=1;
    stk[++stk[0]]=x;
    for(int i=h[x];i;i=a[i].li){
        if(!tp[a[i].nx]){
            tarjan(a[i].nx);
            lw[x]=min(lw[x],lw[a[i].nx]);
        }else if(vis[a[i].nx]){
            lw[x]=min(lw[x],tp[a[i].nx]);
        }
    }if(tp[x]==lw[x]){
        vis[x]=0;
        clr[x]=++clr[0];
        while(stk[stk[0]]!=x){
            clr[stk[stk[0]]]=clr[0];
            vis[stk[stk[0]--]]=0;
        }--stk[0];
    }return;
}

void solve()
{
    for(int i=1;i<=n;++i){
        if(!tp[i]) tarjan(i);
    }for(int i=1;i<=n;++i){
        v[clr[i]].push_back(i);
    }for(int i=1;i<=clr[0];++i){
        if(v[i].size()>maxn){
            maxn=v[i].size();
            ans=i;
        }else if(v[i].size()==maxn){
            if(v[i][0]<v[ans][0]) ans=i;
        }
    }printf("%d\n",maxn);
    for(int i=0;i<v[ans].size();++i){
        printf("%d ",v[ans][i]);
    }return;
}

int main()
{
    init();
    solve();
    return 0;
}