PAT 1146 C++ 版
C++ PAT
2023-09-14 09:13:22 时间
PAT 1146
C++
版
1.题意
给出图的顶点,边信息。再给出几串顶点序列。判断给出的顶点序列是否是该有向图的拓扑序列。
2.分析
- 用一个邻接矩阵作为边信息的存储。
info[maxn][maxn]
- 用一个数组作为顶点度数的存储,
deg[maxn]
- 每次遍历,判断
current vertex
的度数是否为0,如果为0,则从deg[maxn]
中减去current vertex
发出的度数;否则直接跳出
3.代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define maxn 1005
using namespace std;
int info[maxn][maxn];
int main(){
int verNum,edgeNum;
cin >> verNum >> edgeNum;
int i ,j ,k;
int ver1,ver2;
int deg[maxn];//表示每个节点的度
memset(deg,0,sizeof(deg));
for(i = 0;i< edgeNum;i++){
cin >> ver1 >> ver2;//输入的是有向边
info[ver1][ver2] = 1;
deg[ver2]++;//ver2的度数+1
}
int query[maxn];
int queryNum;
cin >> queryNum;
int res[maxn];
int index = 0;
for(i = 0;i< queryNum;i++ ){
for(j = 0;j< verNum;j++){
cin >> query[j];
}
//开始处理各个序列
int degBak[maxn];
for(j = 0;j < verNum + 1; j++){
degBak[j] = deg[j];
}
for( j = 0; j< verNum; j++){
if(degBak[ query[j] ]!=0){//如果入度不为0,则说明不是拓扑排序
res[index++] = i;
break;
}
for(k = 1; k <= verNum;k++){
if(info[query[j]][k] == 1 )//说明顶点 k -> query[j] 之间有边
{
degBak[k]--;//入度减一
}
}
}
}
for(i = 0;i< index;i++){
if (i!=index -1) cout << res[i]<<" ";
else cout << res[i];
}
}
4.测试用例
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
5.执行结果
执行结果如下:
相关文章
- C++多态之析构和纯虚析构分析与示例
- C++string类作为形参传值,实参与形参的变化
- 深入理解C++中的move和forward!
- EasyC++78,动态联编
- 数字逆序输出 -- C++ 实现
- C++中 ostringstream istringstream
- C++map函数的用法_random函数用法
- 使用 C 或 C++ 扩展 Python
- Linus Torvalds:“C++ 真是一门很烂的语言!”
- C/C++——打开文件读取数据的各种方式「建议收藏」
- C++ vector初始化_vector初始化大小
- C++stl库_c++库
- c++ 优先级队列_kafka优先级队列
- C++结构体和类的区别_c++有结构体吗
- C/C++ 关于运算符重载笔记
- c 线程安全的单例模式-C++单例模式(线程安全、内存释放)
- c++版本cef详细使用
- 【错误记录】NDK 配置错误 ( C/C++ debug|arm64-v8a : Could not get version from cmake.dir path )
- C++函数引用传递(超详细)
- 从草根到百万年薪程序员——C/C++职业技能
- 一个更好的C++序列化/反序列化库Kapok
- 深入浅出使用CMySQL编写有效代码(c++ mysql 代码)
- 浅析C++的特殊工具与技术