Uva 10305 - Ordering Tasks 拓扑排序基础水题 队列和dfs实现
今天刚学的拓扑排序，大概搞懂后发现这题是易做图裸的水题。
于是按自己想法敲了一遍，用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>
#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;
}
#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;
}
#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;
}
这次是血淋淋的教训啊：
一、输入部分一定要提前测试
二、测试数据要多一点，多想些特殊测试点
三、必须提高敲题效率。
补充：软件开发 , C++ ,
