• <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 閱讀(197) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 題目分類(lèi):圖論
            久久精品亚洲男人的天堂| 亚洲国产精品高清久久久| 国产精品青草久久久久福利99| 日本福利片国产午夜久久| 精品久久久久久无码中文字幕 | 亚洲一本综合久久| 欧美麻豆久久久久久中文| 久久偷看各类wc女厕嘘嘘| 久久久精品国产Sm最大网站| 午夜精品久久久久久中宇| 亚洲国产精品婷婷久久| 久久久久久国产a免费观看黄色大片| 国产亚洲精久久久久久无码77777| 99久久99久久精品免费看蜜桃| 色综合久久久久网| 久久国产精品无码一区二区三区| 久久精品亚洲精品国产欧美| 人妻无码αv中文字幕久久琪琪布| 大美女久久久久久j久久| 伊人久久大香线蕉综合Av| 国产精品伦理久久久久久| 日韩精品久久无码人妻中文字幕| 精品久久久久一区二区三区| 久久99国产综合精品女同| 综合久久精品色| 久久精品国产精品亚洲人人| 国产精品久久久久国产A级| 亚洲性久久久影院| 久久人人超碰精品CAOPOREN| www.久久99| 999久久久免费精品国产| 日韩人妻无码精品久久免费一| 色播久久人人爽人人爽人人片aV| segui久久国产精品| 久久精品国产秦先生| 国内精品人妻无码久久久影院| 久久强奷乱码老熟女网站| 久久亚洲精品国产精品婷婷| 无码任你躁久久久久久久| 无码精品久久一区二区三区| 久久久久久毛片免费看|