第一次做拓扑排序的题。
题目大意是给定一组字母的大小关系判断它们是否能组成唯一的拓扑序列。
代码写的有点乱,因为思路上比较混乱点。
一般来说,在一个有向无环图中,用 BFS 进行拓扑排序是比较常见的做法
1.把所有入度为 0 的节点放进队列 Q
2 WHILE: Q 不是空队列
3.从 Q 中取出队列首元素 a,把 a 添加到答案的尾部。
4.FOR:所有从 a 出发的边 a → b
5.把 b 的入度减 1。如果 b 的入度变为 0,则把 b 放进队列 Q。
在网上看了很多种版本,有直接用floyd来做的,有用栈的,但我还是比较偏向于用队列+vector来做,这样感觉比较对味。
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int n, m;
int in[60], tmp[60];
char ans[60];
vector<int>v[60];
int top()
{
queue<int>q;
int i, cnt = 0, value = 3; // value等于3 代表可以构成唯一拓扑序列
for(i = 1; i <= n; i++)
if(in[i] == 0)
{
q.push(i);
cnt++;;
}
if(cnt > 1) value = 1; // 说明入度为0的点不唯一,拓扑序列无法确定,但是底下还要找环,所以先不要return
if(cnt == 0) return 2; //找不到入度为0的点,说明一定有环
int ct = 0;
while(!q.empty())
{
int first = q.front();
ans[ct++] = first + 'A' - 1; //存储序列
q.pop();
int size = v[first].size();
cnt = 0;
for(i = 0; i < size; i++)
{
int can_reach = v[first][i];
in[can_reach]--; //将能够连接的点的入度通通都减1
if(in[can_reach] == 0)
{
q.push(can_reach);
cnt++;
}
}
if(cnt > 1) // 入度为0的点不唯一,说明无法确定该序列
return 1;
}
if(ct < n) return 2; //序列个数不够n,说明一定有环
return value; //以上条件都没成立 说明拓扑序列唯一
}
int main()
{
#ifdef LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
char s[5];
int i, x, y, j, res;
while(scanf("%d%d", &n, &m) != EOF)
{
if(n == 0 && m == 0)
break;
memset(in, 0, sizeof(in));
memset(tmp, 0, sizeof(tmp));
memset(ans, 0, sizeof(ans));
for(i = 0; i <= 30; i++)
v[i].clear();
int flag = 0, number;
for(i = 1; i <= m; i++)
{
scanf("%s", s);
x = s[0] - 'A' + 1;
y = s[2] - 'A' + 1;
v[x].push_back(y);
tmp[y]++; //tmp数组的意义是保护所有边得入度不被破坏
for(j = 1; j <= 30; j++)
in[j] = tmp[j];
if(flag == 2 || flag == 3) //有环出现或者拓扑序列已经确定,就不往下进行了
continue;
res = top();
if(i == m && res == 1)
flag = 1;
else if(res == 2)
{
flag = 2;
number = i;
}
else if(res == 3)
{
flag = 3;
number = i;
}
}
if(flag == 1 || m == 0) puts("Sorted sequence cannot be determined.");
else if(flag == 2) printf("Inconsistency found after %d relations.\n", number);
else if(flag == 3)
printf("Sorted sequence determined after %d relations: %s.\n", number, ans);
}
return 0;
}
分享到:
相关推荐
北大POJ1094-Sorting It All Out 解题报告+AC代码
NULL 博文链接:https://200830740306.iteye.com/blog/603488
poj 1091 拓扑排序加上foyld_warshall算法实现
DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...
poj dna sorting 问题,研究的ac coderrrrrrr
北大POJ1936-All in All 解题报告+AC代码
北大POJ1007-DNA Sorting 解题报告+AC代码
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) ... (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
poj 2409 Let it Bead.md
poj 1308 Is It A Tree_.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
POJ上的一道题,我感觉挺难的。分享给大家,这是利用拓扑排序实现,也算是拓扑排序的一道例题。有助于大家对拓排的理解
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告