poj 3660 傳遞閉包 **

題意：題目給出了m對的相對關系，求有多少個排名是確定的。

鏈接：點我

如果這個點到其他點的關系是確定的，那么這個點就是確定的，注意如果這個點到不了其他點，但其他點能到這個點，那么這個點和其他點的關系是確定的

樣例圖：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 #define pb(a) push_back(a)
11 const int INF=0x3f3f3f3f;
12 const double eps=1e-5;
13 typedef long long ll;
14 #define cl(a) memset(a,0,sizeof(a))
15 #define ts printf("*****\n");
16 const int MAXN=110;
17 int n,m,tt,cnt;
18 int g[MAXN][MAXN];
19 int main()
20 {
21     int i,j,k;
22     #ifndef ONLINE_JUDGE
23     freopen("1.in","r",stdin);
24     #endif
25     while(scanf("%d%d",&n,&m)!=EOF)
26     {
27         int a,b;
28         cl(g);
29         for(i=0;i<m;i++)
30         {
31             scanf("%d%d",&a,&b);
32             g[a][b]=1;
33         }
34         for(k=1;k<=n;k++)
35             for(i=1;i<=n;i++)
36                 for(j=1;j<=n;j++)
37                     if(g[i][k]==1&&g[k][j]==1)  g[i][j]=1;
38         int tot=0;
39         for(i=1;i<=n;i++)
40         {
41             bool flag=1;
42             for(j=1;j<=n;j++)
43             {
44                 if(i==j)    continue;
45                 if(g[i][j]==0&&g[j][i]==0)
46                 {
47                     flag=0;
48                     break;
49                 }
50             }
51             if(flag)
52             {
53                 tot++;
54             }
55         }
56         printf("%d\n",tot);
57     }
58 }

轉載于:https://www.cnblogs.com/cnblogs321114287/p/4590269.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/273184.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/273184.shtml
英文地址，請注明出處：http://en.pswp.cn/news/273184.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！