POJ 3660 Cow Contest——flody求传递闭包

POJ 3660 Cow Contest——flody求传递闭包

题意：有n个牛， 他们之间有m个优劣关系， 求有多少个牛的优劣关系完全确定

思路：求出传递闭包后判断每个牛是否和其他所有牛都有关系，是的话ans++

#include #include #include #include using namespace std;const int maxn = 110;int n, m, d[maxn][maxn];int main() { while(~scanf("%d %d", &n, &m)) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { d[i][j] = 0; } } while (m--) { int a, b; scanf("%d %d", &a, &b); d[a][b] = 1; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { d[i][j] = d[i][j] || (d[i][k] && d[k][j]); } } } int ans = 0; for (int i = 1; i <= n; i++) { bool ok = true; for (int j = 1; j <= n; j++) { if (i != j && !d[i][j] && !d[j][i]) { ok = false; break; } } if (ok) ans++; } printf("%d\n", ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。