T9的空間

You will never walk alone!

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

:: 管理 ::

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

<

2008年10月

>

日

一

二

三

四

五

六

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

21

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

公告

如果筆記中有誤導路人的段落，請幫忙email給我，謝謝 shuoxie@gmail.com

隨筆分類

隨筆檔案

搜索

積分與排名

積分 - 49600
排名 - 465

最新評論

1.?re: ACM OJ Collection
評論內容較長,點擊標題查看
--professional resume writing service

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 閱讀(364) 評論(0) 編輯收藏引用所屬分類: Data Structures

只有注冊用戶登錄后才能發表評論。


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

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

T9的空間

公告

隨筆分類

隨筆檔案

相冊

收藏夾

我的鏈接

搜索

積分與排名

最新隨筆

最新評論