• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            題目大意:給出若干個(gè)形如A<B的表達(dá)式,判斷是否出現(xiàn)矛盾、是否能夠確定唯一的一個(gè)序列。
            根據(jù)A<B構(gòu)造圖,出現(xiàn)矛盾即是出現(xiàn)有向環(huán);沒(méi)有矛盾就進(jìn)行拓?fù)渑判颉1绢}需要邊構(gòu)圖邊判斷,在這過(guò)程中,圖可能是不連通的,通過(guò)DFS判斷有向環(huán)比較方便,而用頂點(diǎn)的度來(lái)判斷序列是否唯一比較方便。
            以下是我的代碼:
            #include<iostream>
            #include
            <string>
            #include
            <cstdio>
            #include
            <cstring>
            using namespace std;
            const int kMaxn(27);

            int n,m,g[kMaxn][kMaxn],degree[kMaxn];
            int used[kMaxn];

            bool circle(int u)
            {
                used[u]
            =-1;
                
            for(int i=1;i<=n;i++)
                    
            if(g[u][i])
                    {
                        
            if(used[i]==-1)
                            
            return true;
                        
            else if(used[i]==0 && circle(i))
                            
            return true;
                    }
                used[u]
            =1;
                
            return false;
            }

            bool toposort(string &ansstr)
            {
                
            int d[kMaxn];

                ansstr.clear();
                memcpy(d,degree,kMaxn
            *sizeof(int));
                
            for(int i=1;i<=n;i++)
                {
                    
            int now,cnt(0);
                    
            for(int j=1;j<=n;j++)
                        
            if(d[j]==0)
                        {
                            now
            =j;
                            cnt
            ++;
                        }
                    
            if(cnt>1)
                        
            return false;
                    ansstr
            +=(char)(now+'A'-1);
                    d[now]
            =-1;
                    
            for(int j=1;j<=n;j++)
                        
            if(g[now][j])
                            d[j]
            --;
                }
                
            return (ansstr.size()==n);
            }

            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */

                
            while(scanf("%d%d",&n,&m)==2 && (n || m))
                {
                    
            int anstype(-1),ansvalue;
                    
            string ansstr;
                    memset(g,
            0,kMaxn*kMaxn*sizeof(int));
                    memset(degree,
            0,kMaxn*sizeof(int));
                    
            for(int i=1;i<=m;i++)
                    {
                        
            string t;
                        cin
            >>t;
                        g[t[
            0]-'A'+1][t[2]-'A'+1]=1;
                        degree[t[
            2]-'A'+1]++;

                        memset(used,
            0,kMaxn*sizeof(int));
                        
            if(anstype==-1 && circle(t[0]-'A'+1))
                        {
                            anstype
            =3;
                            ansvalue
            =i;
                        }
                        
            if(anstype==-1 && toposort(ansstr))
                        {
                            anstype
            =1;
                            ansvalue
            =i;
                        }
                    }

                    
            if(anstype==3)
                        printf(
            "Inconsistency found after %d relations.\n",ansvalue);
                    
            else if(anstype==1)
                        printf(
            "Sorted sequence determined after %d relations: %s.\n",ansvalue,ansstr.c_str());
                    
            else
                        printf(
            "Sorted sequence cannot be determined.\n");
                }

                
            return 0;
            }
            posted on 2011-05-27 15:18 lee1r 閱讀(201) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 題目分類(lèi):圖論
            亚洲日韩中文无码久久| 久久影院午夜理论片无码| 精品久久久久久国产牛牛app | 99久久精品国产一区二区| 91久久精品国产成人久久| 99久久国产免费福利| 久久人人爽人人爽人人片AV高清| 国产高潮国产高潮久久久| 色综合色天天久久婷婷基地| 亚洲&#228;v永久无码精品天堂久久 | 欧洲成人午夜精品无码区久久| 99久久中文字幕| 97久久国产综合精品女不卡| 久久免费国产精品一区二区| 人妻少妇精品久久| 免费观看成人久久网免费观看| 2021久久精品免费观看| 亚洲国产日韩欧美综合久久| 久久99久久成人免费播放| 亚洲国产精品无码久久98| 亚洲精品白浆高清久久久久久| 亚洲精品高清久久| 久久av无码专区亚洲av桃花岛| 日韩va亚洲va欧美va久久| 99久久无码一区人妻a黑| 麻豆久久久9性大片| 久久精品无码一区二区三区免费| 91久久精品视频| 97久久天天综合色天天综合色hd| 久久久久免费精品国产| 精品久久久无码中文字幕| 久久综合九色综合97_久久久 | 内射无码专区久久亚洲| 国产欧美一区二区久久| 久久国产精品久久| 国内精品久久人妻互换| 久久人人爽人人爽人人片AV不| 久久伊人五月丁香狠狠色| 欧美日韩中文字幕久久久不卡| 久久综合久久鬼色| 日本WV一本一道久久香蕉|