数据结构实验之图论十:判断给定图是否存在合法拓扑序列(SDUT 2140)
2023-06-13 09:17:22 时间
分析:BFS判断是否有环。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gra[200][200];
int vis[100];
void bfs(int n)
{
memset(vis,0,sizeof(vis));
vis[1] = 1;
int q[100];
int in = 0,out = 0, f = 0;
q[in ++] = 1;
while(in > out)
{
int x = q[out ++];
for(int i = 1; i <= n; i ++)
{
if(gra[x][i])
{
if(vis[i]){
f = 1;
break;
}
else {
vis[i] = 1;
q[in ++] = i;
}
}
}
if(f)break;
}
if(f)printf("NO\n");
else printf("YES\n");
}
int main()
{
int n,m,u,v;
while(scanf("%d%d",&n,&m)!=EOF){
memset(gra,0,sizeof(gra));
for(int i = 0; i < m; i ++){
scanf("%d%d",&u,&v);
gra[u][v] = 1;
}
bfs(n);
}
return 0;
}
相关文章
- 时间序列实践教程总结!
- 2022-08-18:每一个序列都是[a,b]的形式,a < b序列连接的方式为,前一个序列的b,要等于后一个序列的a比如 :
- 时间序列中的特征选择:在保持性能的同时加快预测速度
- 线性反馈移位寄存器的实现原理_线性移位寄存器序列
- 天壤单序列结构预测再获突破!助力生成生物学更快发展
- Java 近期新闻:JDK 21 序列集合、JDK 20 向量 API、Gen ZGC、Hilla 2.0
- 2023-03-31:如何计算字符串中不同的非空回文子序列个数?
- postgreSQL查询结果里添加一个额外的自增序列方法
- MySQL中使用序列Sequence的方式总结
- Python重载运算符实现自定义序列
- SQL Server中新增序列技术实现主键自动增长(sqlserver加序列)
- 精准掌控数据利用Oracle序列伪列实现(oracle使用序列伪列)
- Oracle序列设定实现主键自增长(oracle主键的序列)