比赛 东方幻想乡 S1 评测结果 AAAAAATTTT
题目名称 上白泽慧音 最终得分 60
用户昵称 王者自由 运行时间 4.037 s
代码语言 C++ 内存使用 24.26 MiB
提交时间 2012-08-07 20:45:53
显示代码纯文本
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5000 + 10;
int n, m, a, b, t, p[N], l[N];
bool f[N][N];
int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}
int main() {
    freopen("classroom.in", "r", stdin);
    freopen("classroom.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++) {
        scanf("%d %d %d", &a, &b, &t);
        f[a][b] = 1;
        if(t == 2) f[b][a] = 1;
    }
    for(int i=1; i<=n; i++)
        f[i][i] = 1;
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                f[i][j] |= f[i][k] & f[k][j];
    for(int i=1; i<=n; i++)
        p[i] = i, l[i] = 1;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            if(f[i][j] && f[j][i]) {
                if((a = find(i)) == (b = find(j))) continue;
                p[b] = p[a]; l[a] += l[b];
            }
    int k = 0;
    for(int i=1; i<=n; i++)
        if(l[find(i)] > l[k])
            k = i;
    printf("%d\n", l[k]);
    for(int i=1; i<=n; i++)
        if(find(i) == k)
            printf("%d ", i);
    printf("\n");
    return 0;
}