The Fourth Dimension Space

剛上完數(shù)據(jù)結(jié)構(gòu)課，想練習(xí)一下鄰接表以及拓撲排序，于是找到了這道題，沒想到這道題遠遠不止拓撲排序這么簡單，汗~
PS:這道題用拓撲排序要特別注意，當(dāng)度為零的點>1時，要判斷圖中是否有環(huán)。我就是錯在這里，結(jié)果調(diào)了一個下午。

#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 閱讀(602) 評論(1) 編輯收藏引用

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

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

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

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

評論

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




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理