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

评论

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

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


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