题解 P1726 【上白泽慧音】

非常intresting的一道题

又是一道裸的
太监
不
tarjan的题

模版题坑了我好久，幸好有crn大佬的帮助改错，才救我于苦海之中~ 感谢感谢---

tarjan几次，然后找最大入度的连通块，输出，ok。

贴代码贴代码：

#include<iostream>
using namespace std;
int cnt,chuo=0,n,m,dfn[5001],low[5001],st,a[5001][5001],maxx,bjbj;
int bj[5001],zhan[5001],meat,ment[5001],rd[5001];
void tarjan(int v)
{
    dfn[v]=low[v]=++chuo;
    bj[v]=1;zhan[++st]=v;
    for(int i=1;i<=n;i++)
    if(a[v][i])
    {
        if(!dfn[i])
        {
            tarjan(i);
            low[v]=min(low[v],low[i]);
        }
        else if(bj[i]) low[v]=min(low[v],dfn[i]);
    }
    if(dfn[v]==low[v])
    {
        meat++;
        int y;
        do
        {
            y=zhan[st--];
            bj[y]=0;
            ment[y]=meat;
        }
        while(y!=v);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(z==1) a[x][y]=z;
        else a[x][y]=a[y][x]=z;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++) rd[ment[i]]++;
    for(int i=1;i<=meat;i++)
        if(rd[i]>maxx) maxx=rd[i],bjbj=i;
    cout<<maxx<<endl;
    for(int i=1;i<=n;i++)
        if(ment[i]==bjbj) cout<<i<<" ";
    return 0;
}

P.S.crn大佬用了HEAP，其实不需要啦~~- -