• <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>


            May the force be with you!
            posts - 52,  comments - 33,  trackbacks - 0
                很久沒有在blog上寫解題報(bào)告了。。。前一陣子都在看書,看算導(dǎo),看中大的書。。。差點(diǎn)被認(rèn)為是沒有在做ACM了。。。怪我自己。
                在中大的書上看到一段寫的不錯(cuò)的toplogical sort的代碼,用它來過了一直沒過的1094,后來看到kid的代碼,發(fā)現(xiàn)他寫麻煩了。其實(shí)判環(huán)不用那么麻煩,在拓?fù)渑判蚶锞涂梢耘协h(huán)了。值得注意的是,每次刪點(diǎn)時(shí)都要判斷是否存在兩個(gè)或兩個(gè)以上的入度為0的點(diǎn),因?yàn)檫@樣是不能determin的。如果沒有這一步就會(huì)wa,比如如下數(shù)據(jù):
            4 5
            A<B
            C<D
            B<D
            A<C
            B<D
            若沒有那么做的話,會(huì)在輸出
            Sorted sequence determined after 4 relations:ACBD.
            但是實(shí)際上在第四步還沒有確定。

            代碼比kid的短,呵呵。
                                                    ——Simbaforrest

            代碼如下:
            #include<iostream>
            #include
            <cstring>
            using namespace std;
            int v,e;
            int deg[26];
            int sortAns[26],anstop;
            bool adj[
            26][26];

            int TopSort()
            {
              
            int ret=1;
              bool sure
            =true;
              
            //init
              memset(deg,0,sizeof(deg));
              
            //count degree
              for(int i=0; i<v; i++)
              {
                
            for(int j=0; j<v; j++)
                {
                  
            if(adj[i][j]==true)
                    
            ++deg[j];
                }
              }
              
            //make stack of 0 degree vertex
              int top=-1;
              
            int cnt=0;
              
            for(int i=0; i<v; i++)
              {
                
            if(deg[i]==0)
                {
                  
            ++cnt;
                  deg[i]
            =top;
                  top
            =i;
                }
              }
              
            if(cnt==0)
              {
                sure
            =true;
                
            return ret=-1;//cycle exist
              }
              
            if(cnt>1)
              {
                sure
            =false;
                ret
            =0;//unsure
              }//go on to see if cycle exist
              
              
            //sort
              anstop=-1;
              
            for(int i=0; i<v; i++)
              {
                
            if(top==-1)
                {
                  
            //cycle exist
                  sure=true;
                  
            return ret = -1;
                }
                
            else
                {
                  
            //find j as the 0 degree vertex
                  int j = top;
                  top 
            = deg[top];
                  sortAns[
            ++anstop]=j;//record the ans
                  
                  
            //delete the vertex j
                  cnt=0;
                  
            for(int ni=0; ni<v; ni++)
                  {
                    
            if(adj[j][ni]==true)
                    {
                      
            --deg[ni];
                      
            //a new 0 degree vertex
                      if(deg[ni]==0)
                      {
                        
            ++cnt;
                        deg[ni]
            =top;
                        top 
            = ni;
                      }
                    }
                  }
                  
            if(cnt>1)
                  {
                    sure
            =false;
                    ret
            =0;//unsure
                  }//go on to see if cycle exist
                }
              }
              
            if(sure==false)
                
            return ret=0;
              
            return ret;
            }

            int main()
            {
              
            while(cin>>v>>e,!(v==0&&e==0))
              {
                
            //init
                memset(adj,0,sizeof(adj));
                bool sure
            =false;
                
                
            //read and solve
                for(int i=0; i<e; i++)
                {
                  
            char left,op,right;
                  cin
            >>left>>op>>right;
                  adj[left
            -'A'][right-'A']=1;
                  
                  
            if(sure)
                    
            continue;
                    
                  
            int ret=TopSort();
                  
            if(ret!=0)
                  {
                    sure
            =true;
                    
            if(ret==1)
                    {
                      cout
            <<"Sorted sequence determined after "<<i+1<<" relations: ";
                      
            for(int j=0; j<=anstop; j++)
                        cout
            <<(char)(sortAns[j]+'A');
                      cout
            <<"."<<endl;
                    }
                    
            else if(ret==-1)
                    {
                      cout
            <<"Inconsistency found after "<<i+1<<" relations."<<endl;
                    }
                  }
                }
                
            if(sure==false)
                {
                  cout
            <<"Sorted sequence cannot be determined."<<endl;
                }
              }
              
            return 0;
            }



            posted on 2008-05-15 12:13 R2 閱讀(1450) 評(píng)論(3)  編輯 收藏 引用 所屬分類: Problem Solving

            FeedBack:
            # re: 再談Toplogical sort(pku 1094)
            2009-01-25 01:23 | 風(fēng)之傷
            配上注釋后,相當(dāng)清晰。謝謝大大~~  回復(fù)  更多評(píng)論
              
            # re: 再談Toplogical sort(pku 1094)
            2010-03-06 11:04 | Cinderella
            請(qǐng)問一下 中大的書是哪本書  回復(fù)  更多評(píng)論
              
            # re: 再談Toplogical sort(pku 1094)
            2010-03-06 13:09 | R2
            @Cinderella
            中山大學(xué)郭嵩山老師的《國際大學(xué)生程序設(shè)計(jì)競賽例題解》  回復(fù)  更多評(píng)論
              
            你是第 free hit counter 位訪客




            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術(shù)綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 63675
            • 排名 - 358

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            青青热久久国产久精品| 久久AV高清无码| 久久乐国产精品亚洲综合| 欧美午夜A∨大片久久| 国产精品成人久久久| 久久人妻少妇嫩草AV无码专区| 国产99久久精品一区二区| 国产成人香蕉久久久久| 亚洲熟妇无码另类久久久| 老司机国内精品久久久久| 久久久久久精品免费免费自慰| 欧美精品久久久久久久自慰| 国产高潮国产高潮久久久91| 伊人久久大香线蕉av不卡| 久久97久久97精品免视看| 久久天天躁狠狠躁夜夜躁2O2O| 国产精品女同一区二区久久| 久久一日本道色综合久久| 久久久久无码精品| 99国内精品久久久久久久| 久久久无码精品亚洲日韩按摩 | 色综合久久最新中文字幕| 人妻无码精品久久亚瑟影视| 很黄很污的网站久久mimi色| 精品久久久无码人妻中文字幕豆芽| 久久国产亚洲精品| 亚洲精品综合久久| 亚洲国产成人久久精品99| 国产精品热久久无码av| 久久亚洲国产精品一区二区| 国产精品对白刺激久久久| 久久精品中文騷妇女内射| 色诱久久久久综合网ywww| 免费无码国产欧美久久18| 欧美精品福利视频一区二区三区久久久精品 | 久久嫩草影院免费看夜色| 国产伊人久久| 日韩AV毛片精品久久久| 日本高清无卡码一区二区久久| 久久中文字幕无码专区| 久久这里的只有是精品23|