今天刚学的拓扑排序,大概搞懂后发现这题是赤裸裸的水题。
于是按自己想法敲了一遍,用queue做的,也就是Kahn算法,复杂度o(V+E),调完交上去,WA了。。。
于是检查了一遍又交了一发,还是WA。。。
我还以为是用queue的问题,改成stack也WA,然后干脆放弃STL,手敲了队列,还是WA了。。。
我抓狂了。
感觉没什么问题的,卡了我一个多小时。最后用样例0 1测试,发现是在输入的循环判断时出错了,他要求两个都为0时结束,我只要有一个为0就结束了。。。
坑爹,血的教训。。。
然后我把之前的代码修改后都过了,还尝试了dfs。
于是:
用queue过的:
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 101;
int n, m;
int indegree[maxn] = {0}, gragh[maxn][maxn], res[maxn];
void topologic(void) {
queue <int> q;
int cnt = 0;
for (int i = 0; i < n; i++)
if (indegree[i] == 0)
q.push(i);
while (!q.empty()) {
int tmp = q.front();
q.pop();
res[cnt++] = tmp;
for (int i = 0; i < n; i++)
if (gragh[tmp][i] != 0)
if (--indegree[i] == 0)
q.push(i);
}//while
printf("%d", res[0] + 1);
for (int i = 1; i < cnt; i++)
printf(" %d", res[i] + 1);
printf("\n");
}
int main() {
while (scanf("%d%d", &n, &m) && (n || m)) {
memset(gragh, 0, sizeof(gragh));
memset(indegree, 0, sizeof(indegree));
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
gragh[a-1][b-1] = 1;
indegree[b-1]++;
}//for input
/*
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%d ", gragh[i][j]);
printf("\n");
}
for (int i = 0; i < n; i++)
printf("%d ", indegree[i]);
printf("\n");
*/
topologic();
}//while
return 0;
}
手敲队列:
#include <cstdio>
#include <cstring>
const int maxn = 101;
int g[maxn][maxn], id[maxn], q[maxn];
int main() {
// freopen("in", "r", stdin);
int n, m, a, b, tmp;
int front, tail;
while (scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
memset(g, 0, sizeof(g));
memset(id, 0, sizeof(id));
front = tail = 0;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
g[a][b] = 1;
id[b]++;
}
for (int i = 1; i <= n; i++)
if (id[i] == 0)
q[tail++] = i;
while (tail != front) {
tmp = q[front++];
if (front == 1)
printf("%d", tmp);
else
printf(" %d", tmp);
for (int i = 1; i <= n; i++)
if (g[tmp][i] != 0)
if (--id[i] == 0)
q[tail++] = i;
}//while
printf("\n");
}//while
return 0;
}
dfs方法:
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 101;
int n, m, t;
int gragh[maxn][maxn], res[maxn], c[maxn];
bool dfs(int u) {
c[u] = -1;
for (int v = 0; v < n; v++)
if (gragh[u][v])
if (c[v] < 0)
return false;
else if (!c[v] && !dfs(v))
return false;
c[u] = 1;
res[--t] = u;
return true;
}
bool toposort() {
t = n;
memset(c, 0, sizeof(c));
for (int u = 0; u < n; u++)
if (!c[u])
if (!dfs(u))
return false;
return true;
}
int main() {
while (scanf("%d%d", &n, &m) && (n || m)) {
memset(gragh, 0, sizeof(gragh));
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
gragh[a-1][b-1] = 1;
}//for input
toposort();
for (int i = 0; i < n; i++)
printf("%d ", res[i] + 1);
printf("\n");
}//while
return 0;
}
这次是血淋淋的教训啊:
一、输入部分一定要提前测试
二、测试数据要多一点,多想些特殊测试点
三、必须提高敲题效率。
分享到:
相关推荐
XZ-Ordering_A_Space-Filling Curve.pdf
The-Totem-Single-Ring-Ordering-and-Membership-Protocol.pdf
online-food-ordering-system-源码.rar
分布式文件系统时序,lamport论文,Time-Clocks-and-the-Ordering-of-Events-in-a-Distributed-System.pdf
• Parallel Program and Shared Memory• Parallel Programming in Linux Kernel: Two
DenseNet-40-12-Tensorflow-Backend-TF-dim-ordering.h5 训练完imagenet的权重文件,用此转移学习
假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法,以使得给定有向图G的输入,它的输出是以下两者之一: (a) 一个拓扑排序,于是确定了G为DAG; 或者 (b) G中的一个圈,于是确定了G...
假设给我们一个任意的图,它可能是也可能不是DAG(有向无圈图),推广拓扑排序算法,以使得给定有向图G的输入,它的输出是以下两者之一: (a) 一个拓扑排序,于是确定了G为DAG; 或者 (b) G中的一个圈,于是确定了G...
model weight in this repo https://github.com/fchollet/deep-learning-models Keras提供的预训练权重
TSLint导入组排序规则 强制进口组订购 高度可配置 使用正则表达式配置哪些导入语句进入哪个导入组。 支持确定package.json依赖项(或从node_modules读取所有依赖node_modules ) 有一个自动修复程序 保留评论 ...
cd food-ordering npm install # add DB_URL to the environment variables, it should be a valid postgress connection string npm start # point your browser to localhost:3000 什么? 为什么? 我的同事每个...
Restaurant-Menu-Ordering-System:餐厅菜单点餐系统源代码
Just-pepperoni-app-ordering-api Just Pepperoni的订购系统的API服务 在Node v15.12.0上运行 设置 您的环境将需要安装节点和npm: ://nodejs.org/en/准备好环境后,打开命令行界面(CLI)并运行以下命令(假设您...
Group-Messenger-with-Total-and-FIFO-Ordering 使用 B-multicast 实现带有故障检测的 Total 和 FIFO Ordering。 该项目包括实施 ISIS 算法以维护 TOTAL 订单,我们正在使用该算法基于任何特定仿真器/设备的序列的...
cd fix-franciscan-ordering 添加上游分支并进行任何新更改: git remote add upstream https://github.com/Franciscan-CS-Club/fix-franciscan-ordering git pull upstream main 您已准备好开始! 做出改变 要...
git clone https://github.com/payalpatra/Food-Ordering-System.git 第2步 npm install 步骤3 在根目录中创建.env文件,并使用以下变量名添加您的MongoDB数据库连接URL和Cookie机密 COOKIE_SECRET = ...
Food-ordering-website
简单的在线食品订购系统具有管理端和访问者/客户端。 这是一个易于使用的项目,如果您打算为餐馆或咖啡厅构建或开发点餐系统,那么这个简单的项目将是一个不错的开始。 特征 管理类别 管理菜单 管理类别 管理网站...
为降低移动对象资源的紧张程度,设计了区间计时算法和临界点信息处理算法以降低通信频率,减少响应次数,增强组查询的实时性。在模拟实验中,组查询算法有效降低了移动物体的CPU资源紧张程度和无线通信代价。
rfc3783-iscsi-2004-Command Ordering Considerations with iSCSI