p1232

刚开始真的没想到什么好算法,然后就看到了数据规模,小于5000...这不是在逗我么.

那么就可以支持n^2的算法了,对于每个点跑一次dfs,每个到达的点记录flag[i][now]=1,最后找最大值并输出.

明明是n^2为啥有快超时的啊?不懂

using namespace std;
int i,f,tx,ty,t;
int n,m;
int head[5010],tot,flag[5010][5010],v[5010],sum[5010];
inline void write(int x)  
{  
    if(x<0) putchar('-'),x=-x;  
    if(x>9) write(x/10);  
    putchar(x%10+'0');  
}
inline int read()
{
    int x=0,n=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
     if(ch=='-')n=-1;
     ch=getchar();
 }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*n;
}
struct edge
{
    int x,y,next;
}o[100010];
void add(int x,int y)
{
    tot++;
    o[tot].x=x;
    o[tot].y=y;
    o[tot].next=head[x];
    head[x]=tot;
}
void dfs(int now)
{
    v[now]=1;
    flag[i][now]=1;
    for(int j=head[now];j;j=o[j].next){
        if(v[o[j].y])continue;
        dfs(o[j].y);
    }
}
int main()
{
//freopen("123.in","r",stdin);
//freopen("123.out","w",stdout);
    n=read();m=read();
    for(i=1;i<=m;++i){
        tx=read();
        ty=read();
        t=read();
        add(tx,ty);
        if(t==2)
            add(ty,tx);
    }
    for(i=1;i<=n;++i){
        memset(v,0,sizeof(v));
        dfs(i);
    }
    for(i=1;i<=n;++i)
        for(f=i+1;f<=n;++f)
            if(flag[i][f]&&flag[f][i])
                sum[i]++,sum[f]++;
    for(i=n;i>=1;--i)
        if(sum[i]>sum[0])
            sum[0]=sum[i],t=i;
    write(sum[0]+1);
    putchar(10);
    for(i=1;i<=n;++i)
        if(flag[i][t]&&flag[t][i])
            write(i),putchar(32);
    return 0;
}