 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
原来 当拓扑排序不唯一（当然也就不确定）的时候 还要判断是否有环！ nightKnight 2004-09-15 02:38:00.0 Problem 1094In Reply To:1094求助 Posted by:zouyuanrenren at 2006-04-13 21:53:39 > 感觉算法没有问题
> 依次读入关系，在邻接矩阵中加入边，按出度进行拓扑排序
> 找到出度为0的点
> 若有多个则尚无法排序
> 若没有，则存在环，有矛盾
> 若只有一个，将其删除，同时删除所有指向它的边，并将起加到输出序列中
> 循环，再次找出度为0的点
> 直到所有点都排到输出序列中，即可以排序
> 试了很多测试数据，也找不到错误
> 请各位帮忙看看问题在哪里
>
> #include <iostream>
>
> using namespace std;
>
> short matrix[26][26];
> int n, m;
> int seq[26];
>
> int hamilton()
> // if can be sorted, return 1
> // if inconsistency, return -1
> // other, return 0;
> {
> short image[26][26];
> bool mask[26];
> int i, j;
> int finish = 0;
> int leastnum = 0, least, less;
> // copy the matrix and find the least
> for(i = 0;i < n;i ++)
> {
> mask[i] = 1;
> less = 0;
> for(j = 0;j < n;j ++)
> {
> image[i][j] = matrix[i][j];
> less += matrix[i][j];
> }
> if(less == 0)
> {
> leastnum ++;
> least = i;
> }
> }
> if(leastnum == 0) // circuit found
> return -1;
> if(leastnum > 1)
> return 0;
> while(leastnum == 1)
> {
> seq[finish] = least;
> finish ++;
> for(i = 0;i < n;i ++)
> image[i][least] = 0;
> mask[least] = 0;
> leastnum = 0;
> for(i = 0;i < n;i ++)
> {
> less = 0;
> if(mask[i] == 0)
> continue;
> for(j = 0;j < n;j ++)
> less += image[i][j];
> if(less == 0)
> {
> leastnum ++;
> least = i;
> }
> }
> }
> if(leastnum == 0 && finish == n) // all characters sorted
> return 1;
> if(leastnum == 0)
> return -1;
> return 0;
> }
>
> int main()
> {
> int i, j;
> char left, right;
> bool ic, dt;
> int icnum, dtnum;
> int ham;
> cin>>n>>m;
> while(n + m)
> {
> // initialization
> ic = dt = 0;
> for(i = 0;i < n;i ++)
> {
> for(j = 0;j < n;j ++)
> matrix[i][j] = 0;
> }
> // input the relations and process
> for(i = 0;i < m;i ++)
> {
> cin>>left;
> cin>>right;
> cin>>right;
> if(ic || dt)
> continue;
> matrix[right - 'A'][left - 'A'] = 1;
> ham = hamilton(); // check weather there is a hamilton track existing
> if(ham == 1)
> {
> dt = 1;
> dtnum = i + 1;
> }
> if(ham == -1)
> {
> ic = 1;
> icnum = i + 1;
> }
> }
> if(ic)
> cout<<"Inconsistency found after "<<icnum<<" relations."<<endl;
> else
> {
> if(dt)
> {
> cout<<"Sorted sequence determined after "<<dtnum<<" relations: ";
> for(i = 0;i < n;i ++)
> cout<<char('A' + seq[i]);
> cout<<'.'<<endl;
> }
> else
> cout<<"Sorted sequence cannot be determined."<<endl;
> }
> cin>>n>>m;
> }
> return 0;
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
