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 阅读(569) 评论(1)  编辑 收藏 引用

评论

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

这个题不用再写一个判断环的函数了。
当不存在入度为0的点时即为有环的情况(除了最后所有点均已排序的情况)。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理