比赛 |
东方幻想乡 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;
}