<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

POJ 1093-Sorting It All Out（早知道不用拓撲排序了。。。）

剛上完數據結構課，想練習一下鄰接表以及拓撲排序，于是找到了這道題，沒想到這道題遠遠不止拓撲排序這么簡單，汗~
PS:這道題用拓撲排序要特別注意，當度為零的點>1時，要判斷圖中是否有環。我就是錯在這里，結果調了一個下午。

#include<iostream>

#include<algorithm>

#include<cassert>

#include<cmath>

using namespace std;

#define MAX 100

///////////////////////////////BIGIN_TEMPLATE_BY_ABILITYTAO_ACM///////////////////////////////////////////

template<class T>

class Queue

{

private:

int front,rear;

T *element;

int maxsize;

public:

Queue(int n);

~Queue(){delete []element;}

void push_back(T item);

T pop_front();

T get_front();

void clear(){front=rear=0;}

bool isempty(){return front==rear;}

bool isfull(){return (rear+1)%maxsize==front;}

int lenth(){return (rear-front+maxsize)%maxsize;}

};

template<class T>

Queue<T>::Queue(int n)

{

front=0;

rear=0;

maxsize=n;

element=new T[maxsize];

}

template<class T>

void Queue<T>::push_back( T item)

{

assert(!isfull());

rear=(rear+1)%maxsize;

element[rear]=item;

}

template<class T>

T Queue<T>::pop_front()

{

assert(!isempty());

front=(front+1)%maxsize;

return element[front];

}

template<class T>

T Queue<T>::get_front()

{

assert(!isempty());

return element[(front+1)%maxsize];

}

///////////////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM///////////////////////////////////////////

struct node

{

int adjvex;

node *next;

}adj[MAX];

int indegree[MAX];

int judge[MAX];

Queue<int>a(100000);

Queue<int>b(100000);

int n,m;

void initial()

{

int i;

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

{

adj[i].adjvex=i;

adj[i].next=NULL;

}

}

void addedge()

{

char a,b;

char temp[5];

gets(temp);

a=temp[0];

b=temp[2];

node *p;

p=new node;

p->adjvex=b-'A'+1;

p->next=adj[a-'A'+1].next;

adj[a-'A'+1].next=p;

}

bool judgecircle()

{

Queue<int>temp(1000);

int i;

int mark;

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

{

if(judge[i]==0)

{

temp.push_back(i);

}

}

int count=0;

while(temp.lenth()!=0)

{

count++;

mark=temp.pop_front();

node *p;

for(p=adj[mark].next;p!=NULL;p=p->next)

{

judge[p->adjvex]--;

if(judge[p->adjvex]==0)

temp.push_back(p->adjvex);

}

}

if(count<n)

return 1;

else return 0;

}

int topsort()

{

int i;

node *p;

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

{

indegree[i]=0;

judge[i]=0;

}

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

{

p=adj[i].next;

while(p!=NULL)

{

indegree[p->adjvex]++;

judge[p->adjvex]++;

p=p->next;

}

}

int num=0;

int mark=0;

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

{

if(indegree[i]==0)

{

num++;

mark=i;

}

}

if(num>1)

{

if(judgecircle()==true)

return 0;

return 2;

}

else if(num==0)

return 0;

a.push_back(mark);

while(a.lenth()!=0)

{

num=0;

mark=0;

node *p;

int k=a.get_front();

b.push_back(a.pop_front());

if(b.lenth()==n)

return 1;

for(p=adj[k].next;p!=NULL;p=p->next)

{

indegree[p->adjvex]--;

if(indegree[p->adjvex]==0)

{

num++;

mark=p->adjvex;

}

}

if(num>1)

return 2;

else if(num==0)

return 0;

else if(num==1)

{

a.push_back(mark);

}

}

}

int main()

{

int k;

int result=0;

int flag;

int mark;

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

{

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

break;

result=0;

initial();

cin.ignore();

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

{

if(result==0)

{

a.clear();

b.clear();

}

addedge();

if(result==0)

{

flag=topsort();

mark=k;

}

if(flag==1)

result=1;

else if(flag==0)

result=2;

else if(flag==2)

continue;

}

if(result==1)

{

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

while(b.lenth()!=0)

printf("%c",b.pop_front()+'A'-1);

printf(".\n");

}

else if(result==2)

{

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

}

else if(result==0)

{

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

}

}

system("pause");

return 0;

}

posted on 2009-04-04 01:05 abilitytao 閱讀(585) 評論(1) 編輯收藏引用

評論

# re: POJ 1093-Sorting It All Out（早知道不用拓撲排序了。。。） 2009-11-26 10:53 upwinder

這個題不用再寫一個判斷環的函數了。
當不存在入度為0的點時即為有環的情況(除了最后所有點均已排序的情況)。回復更多評論

刷新評論列表

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



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

久久精品国产亚洲欧美| 一本一本久久A久久综合精品| 久久久久久久精品妇女99| 国产精品VIDEOSSEX久久发布| 2021久久国自产拍精品| 国产精品18久久久久久vr| 久久婷婷五月综合97色一本一本| 亚洲色婷婷综合久久| 色婷婷久久综合中文久久蜜桃av| 一本色道久久综合亚洲精品| 亚洲AV无码久久| 久久久久免费看成人影片| 人妻无码αv中文字幕久久琪琪布人妻无码久久一区二区三区免费人妻无码中文久久久久专区 | 精品综合久久久久久97超人| 91精品国产综合久久久久久| 日本一区精品久久久久影院| 2021国产成人精品久久| 久久久久久国产精品无码下载| 青青草原综合久久大伊人导航 | 韩国三级大全久久网站| 久久精品9988| 亚洲va久久久久| 丰满少妇高潮惨叫久久久| 91性高湖久久久久| 欧美亚洲国产精品久久| 久久A级毛片免费观看| 久久99精品久久久久久水蜜桃 | 中文字幕成人精品久久不卡| 久久国产精品二国产精品| 一本一道久久综合狠狠老 | 久久久久久九九99精品| 人人狠狠综合久久亚洲88| 欧美午夜A∨大片久久 | 伊人久久大香线蕉影院95| 亚洲国产成人久久笫一页| 韩国免费A级毛片久久| 久久综合精品国产一区二区三区| 久久青青草原亚洲av无码app| 精品综合久久久久久88小说| 欧美熟妇另类久久久久久不卡| 大美女久久久久久j久久|