• <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的點時即為有環的情況(除了最后所有點均已排序的情況)。  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



久久久久99精品成人片试看|
婷婷久久综合|
久久人与动人物a级毛片|
99久久无码一区人妻|
国产精品久久久久久影院|
中文字幕乱码人妻无码久久|
中文字幕无码久久人妻|
久久99久久99精品免视看动漫|
久久99热这里只有精品国产|
99久久国产亚洲高清观看2024|
色偷偷888欧美精品久久久|
久久夜色tv网站|
2020最新久久久视精品爱|
国产福利电影一区二区三区久久老子无码午夜伦不
|
久久精品国产只有精品2020
|
国产亚洲色婷婷久久99精品|
国产亚洲精品美女久久久|
国产69精品久久久久777|
久久午夜电影网|
无码国内精品久久人妻麻豆按摩|
亚洲国产成人乱码精品女人久久久不卡
|
漂亮人妻被黑人久久精品|
99久久精品日本一区二区免费|
久久99国产精品久久|
久久本道久久综合伊人|
青青草原综合久久大伊人|
2021精品国产综合久久|
久久人人爽人人澡人人高潮AV
|
久久777国产线看观看精品|
久久这里只有精品首页|
亚洲国产天堂久久久久久|
欧美熟妇另类久久久久久不卡|
狠狠色丁香婷婷久久综合不卡|
久久亚洲中文字幕精品一区|
久久久久国产精品熟女影院
|
久久r热这里有精品视频|
亚洲日本va午夜中文字幕久久|
精品国产VA久久久久久久冰
|
国产精品久久国产精麻豆99网站|
久久久久国色AV免费观看|
久久不见久久见免费视频7|