首页 > 代码库 > POJ3660-Permutations-传递闭包FLOYD

POJ3660-Permutations-传递闭包FLOYD

2024-08-16 18:16:18   210人阅读

【题目大意】给出二元关系，此关系满足传递性，求其中与其余元素关系确定的元素个数。

【解题思路】对此关系进行传递闭包运算。用邻接矩阵储存。用Floyd更新关系。对于元素i找出 第i行 和 第i列 中关系确定的个数，若==（n-1） 则ans++；
 1 #include "cstdio" 2 #include "iostream" 3 #include "cstring" 4 using namespace std; 5 int  E[105][105]; 6 int main() 7 { 8     int n , m; 9     cin >> n >> m;10     memset(E, 0, sizeof(E));11     for (int i = 1 ; i <= n ; i++)12     {13         E[i][i] = 1;14     }15     for (int i = 1 ; i <= m; i++)16     {17         int a, b;18         scanf("%d%d", &a, &b);19         E[a][b] = 1;20     }21     for (int k = 1; k <= n ; k++)22         for (int i = 1; i <= n ; i++)23             for (int j = 1; j <= n ; j++)24                 if ((E[i][k]) && (E[k][j])) E[i][j] = 1;25 26     int ans = 0, j;27     for (int i = 1 ; i <= n ; i++)28     {29         for( j = 1; j <= n; j++)30             if (E[i][j] + E[j][i] == 0) break;31         if (j > n) ans++;32     }33     cout << ans << endl;34 }

 

POJ3660-Permutations-传递闭包FLOYD


联系
我们