P13321 [GCJ 2012 #1C] Diamond Inheritance Solution¶

题目传送门 P13321 [GCJ 2012 #1C] Diamond Inheritance

思路¶

本题要求我们判断给定的继承关系图中是否存在 菱形继承 。菱形继承指的是在图中是否存在两个类 \(X\) 和 \(Y\)，使得从 \(X\) 到 \(Y\) 存在至少两条不同的继承路径。

我们可以考虑使用 dfs 来遍历每个类的所有路径。对于每个类，我们需要检查是否存在某个类被通过多条不同路径继承，如果超过一次，即可直接返回输出 Yes，反之输出 No。

Code¶

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int MAXN = 1010;
vector<int> mp[MAXN];
bool vis[MAXN];
bool flg;

void dfs(int u) {
    if (flg) return;
    vis[u] = true;
    for (int v : mp[u]) {
        if (vis[v]) {flg = 1;return;}
        dfs(v);
    }
}

void solve() {
    int T;cin >> T;
    for (int t = 1; t <= T; ++t) {
        int N; cin >> N;
        for (int i = 1; i <= N; ++i) mp[i].clear();

        for (int i = 1; i <= N; ++i) {
            int M;cin >> M;
            for (int j = 0; j < M; ++j) {
                int fat;cin >> fat;
                mp[i].pb(fat);
            }
        }

        flg = 0;
        for (int i = 1; i <= N && !flg; ++i) {
            memset(vis, 0, sizeof(vis));
            dfs(i);
        }

        cout << "Case #" << t << ": " << (flg ? "Yes" : "No") << endl;
    }
}

int main() {
    solve();
    return 0;
}