T9的空間

You will never walk alone!

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

69 隨筆 :: 0 文章 :: 28 評論 :: 0 Trackbacks

POJ 1094 Topological_Sort（拓撲排序）

Source Code

Problem: 1094 User: Torres

Memory: 224K Time: 32MS

Language: C++ Result: Accepted

Source Code

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

#define N 30

vector<vector<int> > G(N);

int re[N];

int Top_sort(vector<vector<int> >G,int n,int *de)

{

//out<<"www"<<endl;

int i,j,k;

memset(re,0,sizeof(re));

int cnt=0;

int flag1=0;

for(i=0;i<n;i++)

{

int flag=0;

for(j=0;j<n;j++)

{

if(de[j]==0)

{

flag=1;

for(k=j+1;!flag1&&k<n;k++)

if(de[k]==0)

{

flag1=1;

break;

}

//說明有兩個可供選擇的點那么就會產生不同的排列

re[cnt++]=j;

de[j]=-1;

int len=G[j].size();

for(k=0;k<len;k++)

if(de[G[j][k]]>0) de[G[j][k]]--;

break;

}

if(!flag) return 1;//矛盾

}

if(flag1) return -1;//不確定

return 0;//正常

}

int main()

{

int n,m,i;

char s[4];

//freopen("in.txt","r",stdin);

while(scanf("%d%d",&n,&m))

{

if(n==0&&m==0) break;

int de[N]={0},d[N];

int t;

for(t=1;t<=m;t++)

{

scanf("%s",s);

G[s[0]-'A'].push_back(s[2]-'A');

de[s[2]-'A']++;

// for(i=0;i<n;i++)

// cout<<de[i]<<endl;

memcpy(d,de,sizeof(de));

int ans=Top_sort(G,n,d);

if(ans==1)

{

printf("Inconsistency found after %d relations.\n",t);

while(t<m) scanf("%s",s),t++;

}

else if(ans==0)

{

printf("Sorted sequence determined after %d relations: ",t);

for(i=0;i<n;i++)

printf("%c",re[i]+'A');

printf(".\n");

while(t<m) scanf("%s",s),t++;

}

else if(t==m&&ans==-1)

printf("Sorted sequence cannot be determined.\n");

}

for(i=0;i<n;i++)

G[i].clear();

}

return 0;

}

posted on 2008-10-20 22:18 Torres 閱讀(352) 評論(0) 編輯收藏引用所屬分類: Data Structures

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 算法導論讀書筆記. 快速排序歸并排序 My_heap POJ 1094 Topological_Sort（拓撲排序）拓撲排序—數據結構嚴蔚敏p173 POJ3253(赫夫曼樹) POJ1686（棧）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

T9的空間

公告

隨筆分類

隨筆檔案

相冊

收藏夾

我的鏈接

搜索

積分與排名

最新隨筆

最新評論