Diamond
quoc14
c_cpp
20 days ago
3.9 kB
6
Indexable
Never
DFS and BFS
Level 4 Diamond You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y. In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C1, C2, C3, ..., Cn, Y where X inherits from C1, Ci inherits from Ci + 1 for 1 ≤ i ≤ n - 1, and Cn inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A. A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance. Input The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines follow. The ith line starts with a non-negative integer Mi indicating the number of classes that class i inherits from. This is followed by Mi distinct positive integers each from 1 to N representing those classes. You may assume that: If there is an inheritance path from X to Y then there is no inheritance path from Y to X. A class will never inherit from itself. Output For each diagram, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is "Yes" if the class diagram contains a diamond inheritance, "No" otherwise. Limits 1 ≤ T ≤ 50. 0 ≤ Mi ≤ 10. Small dataset 1 ≤ N ≤ 50. Large dataset 1 ≤ N ≤ 1,000. Sample Input 3 3 1 2 1 3 0 5 2 2 3 1 4 1 5 1 5 0 3 2 2 3 1 3 0 Output Case #1 No Case #2 Yes Case #3 Yes Case #1 No Case #2 Yes Case #3 Yes Case #4 No Case #5 No Case #6 Yes Case #7 No Case #8 Yes Case #9 Yes Case #10 Yes Case #11 No Case #12 Yes Case #13 Yes Case #14 No Case #15 No Case #16 Yes Case #17 No Case #18 Yes Case #19 Yes Case #20 Yes Case #21 Yes Case #22 Yes Case #23 Yes Case #24 Yes Case #25 Yes Case #26 Yes Case #27 Yes Case #28 Yes Case #29 Yes Case #30 Yes Case #31 Yes Case #32 Yes Case #33 No Case #34 Yes Case #35 No Case #36 No Case #37 Yes Case #38 Yes Case #39 No Case #40 Yes Case #41 No Case #42 Yes Case #43 No Case #44 No Case #45 No Case #46 No Case #47 No Case #48 No Case #49 No Case #50 No #include <iostream> using namespace std; int T, n, m, vCnt; bool result; int mp[1001][1001], cnt[1001], vs[1001]; void dfs(int v){ if(result) return; for(int i = 0; i < cnt[v]; i++){ if(vs[mp[v][i]] == 0){ vs[mp[v][i]]++; dfs(mp[v][i]); } else { result = true; break; } } } int main(){ freopen("input.txt", "r", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ // Input cin >> n; for(int i = 1; i <= n; i++){ cin >> cnt[i]; for(int j = 0; j < cnt[i]; j++){ cin >> mp[i][j]; } } // Initial result = false; // Solve Problem for(int i = 1; i <= n; i++){ for(int j = 1; j <=n; j++) vs[j] = 0; for(int j = 0; j < cnt[i]; j++){ if(vs[mp[i][j]] >= 1){ result = true; break; } else{ vs[i]++, vs[mp[i][j]]++; dfs(mp[i][j]); } } if(result) break; } // Output cout << "Case #" << tc << endl << (result ? "Yes" : "No") << endl; } return 0; }
Leave a Comment