题解：P13321 [GCJ 2012 #1C] Diamond Inheritance

_czl_ · 2025-07-17 19:37:03 · 题解

题解：P13288 [GCJ 2013 #1B] Osmos

题目Link

思路

图论题。没接触过图论的出门左转：图的存储。

首先简化题意：给定一个有向图，判断是否存在两个不同的路径从节点 X 到达节点 Y。

考虑图论。首先使用链式前向星建图，然后对每一个节点 u 做深搜，记录能到达的所有节点，并在访问过程中统计是否某个节点被访问了两次。

时间复杂度 O(N^2)。

Code

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
int T,n,m,x,y,cnt,head[10005];
struct E{
    int to,nxt;
}e[10005];
int vis[10005],f;
void ad(int u,int v)
{
    e[cnt]={v,head[u]},head[u]=cnt++;//建图
}
void dfs(int u,int tag)//寻找路径
{
    if(f) return;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v]==tag){
            f=1;
            return;
        }
        vis[v]=tag;
        dfs(v,tag);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        cnt=0;
        memset(head,-1,sizeof head);
        cin>>n;
        for(int u=1;u<=n;u++)
        {
            cin>>m;
            while(m--){
                cin>>x;
                ad(u,x);//建边
            }
        }
        int ans=0;
        for(int u=1;u<=n&&!ans;u++)
        {
            memset(vis,0,sizeof vis);
            f=0;
            dfs(u,u);
            if(f)ans=1;//存在菱形路径
        }
        cout<<"Case #"<<i<<": "<<(ans?"Yes":"No")<<"\n";
    }
    return 0;
}