poj 1094 Sorting It All Out Folyd+dfs拓扑排序

每接受一组关系,用Floyd算法计算传递闭包,

判断是否有矛盾:if(adj[i][j]&&adj[j][i])isInconsitent=true;

判断是否有关系未确定:if(adj[i][j]==0&&adj[j][i]==0&&(i!=j))issorted=false;

如果没有矛盾,所以关系确定,则说明已经sort好了,用dfs拓扑排序输出即可。

然后把未接受的数据接受完,刚开始直接跳出了。


#include<iostream>
#include
<cstring>
#include
<vector>
using namespace std;
bool adj[27][27]; int n,m;
bool visit[27],isInconsitent=false,issorted=true;
vector
<int>vec;
void Floyd()
{
    
int i,j,k;
    
for(k=1; k<=n; k++)
        
for(i=1; i<=n; i++)
            
for(j=1; j<=n; j++)
                 adj[i][j]
= (adj[i][j]||adj[i][k]&&adj[k][j]);
}

void check()
{
    isInconsitent
=false,issorted=true;
    
int i,j;
    
for(i=1; i<=n; i++)
        
for(j=1; j<=n; j++)
        {
            
if(adj[i][j]&&adj[j][i])isInconsitent=true;
            
if(adj[i][j]==0&&adj[j][i]==0&&(i!=j))issorted=false;
        }
}

void dfs(int i)
{
    visit[i]
=true;
    
for(int j=1; j<=n; j++)
        
if(!visit[j]&&adj[i][j])
            dfs(j);
    vec.push_back(i);
}
int main()
{
    
while(cin>>n>>m)
    {
        
if(n==0&&m==0)break;
        memset(adj,
0,sizeof adj);
        
bool print=false;
        
int i,j;
        
char pre,last,less;
        
for(i=1; i<=m; i++)
        {
            cin
>>pre>>less>>last;
            adj[
int(pre-'A'+1)][int(last-'A'+1)]=true;
            
            Floyd();

            check();
            
            
if(isInconsitent)
            {
                cout
<<"Inconsistency found after "<<i<<" relations."<<endl;
                print 
=truebreak;
            }

            
if(issorted)
            {
                cout
<<"Sorted sequence determined after "<<i<<" relations: ";
                vec.clear();
                memset(visit,
0,sizeof visit); 
                
for(int t=1; t<=n; t++)
                    
if(!visit[t])dfs(t); 
                
while(vec.size())
                {
                    cout
<<char(vec[vec.size()-1]+'A'-1);
                    vec.pop_back(); 
                }
                cout
<<'.'<<endl;
                print
=truebreak;
            }
            
        }
        
if(print==false)cout<<"Sorted sequence cannot be determined."<<endl;
        
//accept the data left
        for(j=i+1; j<=m; j++)
            cin
>>pre>>less>>last;
    }

    
return 0;
}

posted on 2010-08-17 10:26 田兵 阅读(200) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜