专栏文章

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

__czl_
P13321题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miouy6mk
此快照首次捕获于
2025/12/03 01:34
3 个月前
此快照最后确认于
2025/12/03 01:34
3 个月前
查看原文

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

题目Link

思路

图论题。没接触过图论的出门左转：图的存储。
首先简化题意：给定一个有向图，判断是否存在两个不同的路径从节点 XX 到达节点 YY。
考虑图论。首先使用链式前向星建图，然后对每一个节点 uu 做深搜，记录能到达的所有节点，并在访问过程中统计是否某个节点被访问了两次。
时间复杂度 O(N2)O(N^2)。

Code

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...