首页 > 代码库 > UVa11175 From D to E and Back (结论)

UVa11175 From D to E and Back (结论)

2024-08-14 11:45:05   210人阅读

 链接：http://bak2.vjudge.net/problem/UVA-11175

分析：AE->EB&&CE->EB说明AE和CE都在用E表示的集合中，那么AE连向任何一个结点，CE也必定有向那个结点连边。总结：如果存在i和j都有连向k1的边，而i和j中只有一个结点连向k2，那么这个有向图E是不可能由有向图D转化来的。

技术分享

 

 

 

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4  5 const int maxn = 300 + 5; 6  7 int m, k; 8 int G[maxn][maxn]; 9 10 int main() {11     int T;12     scanf("%d", &T);13     for (int kase = 1; kase <= T; kase++) {14         memset(G, 0, sizeof(G));15         scanf("%d%d", &m, &k);16         while (k--) {17             int x, y;18             scanf("%d%d", &x, &y);19             G[x][y] = 1;20         }21         bool ok = true;22         for (int i = 0; i < m; i++)23             for (int j = i + 1; j < m; j++) {24                 int f1 = 0, f2 = 0;25                 for (int k = 0; k < m; k++) {26                     if (G[i][k] && G[j][k]) f1 = 1;27                     if (G[i][k] ^ G[j][k]) f2 = 1;28                 }29                 if (f1 && f2) { ok = false; break; }30             }31         printf("Case #%d: ", kase);32         if (ok) printf("Yes\n");33         else printf("No\n");34     }35     return 0;36 }

 

UVa11175 From D to E and Back (结论)


联系
我们