• <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（早知道不用拓撲排序了。。。）
		
            
		剛上完數(shù)據(jù)結(jié)構(gòu)課，想練習一下鄰接表以及拓撲排序，于是找到了這道題，沒想到這道題遠遠不止拓撲排序這么簡單，汗~
            PS:這道題用拓撲排序要特別注意，當度為零的點>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 閱讀(594) 評論(1)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

            評論
            
	
	
			
            
				# re: POJ 1093-Sorting It All Out（早知道不用拓撲排序了。。。）
					
						2009-11-26 10:53
					
				upwinder
			
            
			
            
				這個題不用再寫一個判斷環(huán)的函數(shù)了。

            當不存在入度為0的點時即為有環(huán)的情況(除了最后所有點均已排序的情況)。  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



国内精品伊人久久久影院|
麻豆av久久av盛宴av|
狠狠综合久久综合88亚洲
|
亚洲精品白浆高清久久久久久|
久久久久国产|
久久久久这里只有精品|
久久婷婷人人澡人人|
久久久久国产视频电影|
久久精品国产第一区二区|
久久精品国产清自在天天线|
日日狠狠久久偷偷色综合96蜜桃|
久久久久久极精品久久久|
久久一本综合|
97精品国产97久久久久久免费|
无码人妻久久一区二区三区蜜桃|
久久久无码精品亚洲日韩京东传媒|
中文字幕无码av激情不卡久久|
久久精品中文字幕大胸|
欧美一区二区三区久久综|
1000部精品久久久久久久久|
国产精品热久久毛片|
亚洲人成精品久久久久|
狠狠狠色丁香婷婷综合久久五月
|
久久精品国产亚洲AV无码娇色|
国产精品一区二区久久国产|
91久久香蕉国产熟女线看|
欧美精品丝袜久久久中文字幕
|
久久久久人妻一区二区三区|
久久99热只有频精品8|
99久久无码一区人妻|
欧美精品乱码99久久蜜桃|
精品久久久久久久|
久久久WWW免费人成精品|
久久久久亚洲精品天堂|
久久精品国产亚洲Aⅴ蜜臀色欲|
日本五月天婷久久网站|
日本一区精品久久久久影院|
国产毛片欧美毛片久久久|
精品久久久久久久中文字幕|
狠狠色狠狠色综合久久|
久久久精品视频免费观看|