青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 33,  comments - 33,  trackbacks - 0
題意:如果單詞A的結(jié)尾字母與單詞B的首字母相同,那么可以認為是A到B相通。給出一系列單詞,求這些詞按照某種排列能否串通。
題解:
如果直接按照題意建模,以單詞為頂點,邊表示兩兩相通,那么將會得到哈密頓回路模型。顯然是很難解的。
換一種方式,以字母為頂點,邊表示傳送的單詞,那么就得到歐拉回路模型的圖,可以按照歐拉定理求解。
以下給出Euler圖的相關(guān)知識:
Euler回路:G中經(jīng)過每條邊一次且僅一次的回路
Euler路徑:G中經(jīng)過每條邊一次且僅一次的路徑
無向圖存在Euler回路定理:當它是連通圖+頂點度數(shù)為偶數(shù)
無向圖存在Euler路徑定理:當它是連通圖+除兩個頂點度為奇數(shù)外,其余為偶數(shù)
有向圖存在Euler回路定理:當它是連通圖+頂點入度 == 出度
有向圖存在Euler路徑定理:當它是連通圖+除一個頂點的入度和出度的差的絕對值小1外,其余相等
代碼:
#include <stdio.h>
#include 
<string.h>
const int N = 30;

class UnionSet
{
private:
    
int parent[N];
    
int rank[N];
    
int size;
public:
    UnionSet(
int _size):size(_size)
    
{
        init();
    }

    
~UnionSet()
    
{
    }


    
void init()
    
{
        
for(int i = 0; i < size; ++i)
        
{
            parent[i] 
= -1;
            rank[i] 
= 1;
        }

    }


    
int root(int _x)
    
{
        
int r = _x;
        
while(parent[r] >= 0)
            r 
= parent[r];
        
int i = _x;
        
int j;
        
while(parent[i] >= 0)
        
{
            j 
= parent[i];
            parent[i] 
= r;
            i 
= j;
        }

        
return r;
    }


    
int Union(int _r1,int _r2)
    
{
        
if(_r1 == _r2)
            
return _r1;
        
else
        
{
            
int root1 = root(_r1);
            
int root2 = root(_r2);
            
if(root1 == root2)
                
return root1;
            
if(rank[root1] > rank[root2])
            
{
                parent[root2] 
= root1;
                rank[root1] 
+= rank[root2];
            }

            
else
            
{
                parent[root1] 
= root2;
                rank[root2] 
+= rank[root1];
            }

        }

    }

    
int getRank(int _x)
    
{
        
return rank[_x];
    }

}
;
char buf1[1024];

void Test()
{
    
int In[30= {0};
    
int Out[30= {0};
    
bool visited[30= {false};
    UnionSet Set(
28);
    
int n;
    scanf(
"%d",&n);
    
bool flag = false;
    
int start = 0;
    
for (int i = 0; i < n; ++i)
    
{
        scanf(
"%s",buf1);
        
int len = strlen(buf1);
        Set.Union(buf1[
0- 'a',buf1[len-1- 'a');
        In[buf1[len
-1- 'a']++;
        Out[buf1[
0- 'a']++;
        visited[buf1[
0- 'a'= true;
        visited[buf1[len
-1- 'a'= true;
        
if (!flag)
        
{
            start 
= buf1[0- 'a';
            flag 
= true;
        }

    }

    
    
for (int i = 0; i < 26++i)
    
{
        
if (i != start)
        
{
            
if (visited[i] && (Set.root(start) != Set.root(i)))
            
{
                printf(
"The door cannot be opened.\n");
                
return;
            }

        }

    }

    
int cntIn = 0;
    
int cntOut = 0;
    
for (int i = 0; i < 26++i)
    
{
        
if (visited[i])
        
{
            
if (In[i] != Out[i])
            
{
                
if (In[i] - Out[i] == -1)
                
{
                    cntIn
++;
                }

                
else if (In[i] - Out[i] == 1)
                
{
                    cntOut
++;
                }

                
else
                
{
                    printf(
"The door cannot be opened.\n");
                    
return;
                }

            }

        }

    }

    
if ((cntIn != cntOut)||((cntIn == cntOut)&&(cntIn > 1)))
    
{
        printf(
"The door cannot be opened.\n");
    }

    
else
        printf(
"Ordering is possible.\n");
}


int main()
{
    
//freopen("data.txt","r",stdin);
    int tc;
    scanf(
"%d",&tc);
    
for (int i = 0; i < tc; ++i)
    
{
        Test();
    }

    
return 0;
}

posted on 2011-06-02 11:56 bennycen 閱讀(1550) 評論(0)  編輯 收藏 引用

只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产日韩一区二区| 久久精品在线视频| 久久电影一区| 欧美资源在线观看| 毛片基地黄久久久久久天堂| 狂野欧美激情性xxxx欧美| 久久综合国产精品| 蜜乳av另类精品一区二区| 欧美国产日韩一区二区在线观看 | 久久综合中文字幕| 欧美经典一区二区三区| 欧美日韩一区在线视频| 国产日韩欧美亚洲一区| 一区二区三区在线观看欧美| 亚洲精品久久久久久久久久久久 | 国产精品三上| 在线日韩中文| 性久久久久久久久| 美日韩精品免费| 亚洲精品精选| 午夜欧美大片免费观看 | 韩国成人理伦片免费播放| 亚洲欧洲精品一区| 性欧美长视频| 亚洲欧洲精品天堂一级| 欧美一区二视频在线免费观看| 中文网丁香综合网| 国产日韩精品一区二区| 91久久在线播放| 久久er99精品| 亚洲美女av黄| 免费h精品视频在线播放| 国产精品欧美日韩| 一本久久a久久免费精品不卡| 久久精品欧美日韩精品| 一区二区三区福利| 久久综合色综合88| 国产一区二区三区无遮挡| 一区二区高清在线| 欧美高清在线一区| 久久激情五月激情| 国产精品你懂的在线| 这里是久久伊人| 亚洲国产天堂久久综合| 久久综合伊人| 亚洲福利国产精品| 毛片一区二区| 久久精品视频在线| 国内精品久久久久影院色| 香蕉免费一区二区三区在线观看| 亚洲国产一二三| 欧美精品亚洲精品| 亚洲美女在线视频| 亚洲国产精品久久人人爱蜜臀| 久久久久久夜| 亚洲电影av| 亚洲电影免费观看高清完整版在线 | 亚洲天堂av综合网| 99精品福利视频| 欧美日韩在线播| 亚洲一区二区三区精品动漫| 欧美激情国产日韩精品一区18| 久久av免费一区| 亚洲电影免费观看高清完整版在线观看| 欧美在线影院在线视频| 亚洲欧美资源在线| 今天的高清视频免费播放成人| 久久亚洲春色中文字幕| 久久国产99| 亚洲国产视频一区二区| 最新亚洲电影| 国产精品亚洲综合一区在线观看| 香蕉久久夜色精品国产| 久久精品国产精品亚洲综合| 在线播放日韩欧美| 亚洲国产精品999| 国产精品福利在线观看| 久久不射网站| 欧美成人日本| 午夜精品福利视频| 久久久久国产精品www| 亚洲人成欧美中文字幕| 一区二区三区偷拍| 久久久91精品国产| 亚洲精品日韩精品| 国产精品免费一区豆花| 久久精品视频在线| 蜜臀久久99精品久久久画质超高清| 亚洲三级视频在线观看| 亚洲视频一区| 亚洲国产精品视频一区| 亚洲精品美女在线| 国产亚洲视频在线观看| 亚洲高清一区二区三区| 国产精品日韩一区| 欧美高清自拍一区| 国产日本欧洲亚洲| 亚洲三级电影在线观看 | 亚洲精品一区在线观看| 亚洲一区二区三区在线观看视频 | 欧美在线观看一二区| 久久中文欧美| 欧美在线播放视频| 欧美激情亚洲| 欧美aⅴ一区二区三区视频| 国产精品一区二区久久| 亚洲欧洲另类国产综合| 一区二区在线观看av| 亚洲综合导航| 亚洲午夜久久久| 免费短视频成人日韩| 久久精品国产v日韩v亚洲 | 欧美一级日韩一级| 欧美日本不卡高清| 亚洲国产精品国自产拍av秋霞| 国产一区二区三区在线观看精品 | 一区二区三区三区在线| 久久婷婷一区| 久久久久久网站| 国产欧美日韩另类一区 | 一个人看的www久久| 日韩小视频在线观看专区| 快射av在线播放一区| 美女视频黄a大片欧美| 国产精品拍天天在线| 99re66热这里只有精品4| 91久久午夜| 欧美激情精品| 91久久国产综合久久蜜月精品 | 亚洲国产视频一区二区| 欧美日韩在线看| 亚洲精品国产精品国自产观看浪潮| 国产一区二区三区不卡在线观看| 亚洲影视九九影院在线观看| 亚洲一区日韩| 国产精品美女一区二区| 亚洲一区二区免费| 久久国产欧美精品| 国产在线不卡精品| 欧美一级淫片aaaaaaa视频| 新67194成人永久网站| 国产女人精品视频| 欧美一区中文字幕| 免费亚洲电影在线| 亚洲国产乱码最新视频| 欧美~级网站不卡| 亚洲精品欧美激情| 香蕉久久夜色| 国外成人在线视频| 免费观看日韩| 夜夜嗨av色综合久久久综合网 | 欧美阿v一级看视频| 亚洲精品免费在线播放| 欧美日韩伊人| 亚洲欧美一区在线| 欧美成人三级在线| 亚洲视频高清| 国产在线观看一区| 欧美二区在线观看| 亚洲午夜免费福利视频| 久久综合伊人77777| 日韩视频一区二区在线观看| 国产精品99一区二区| 欧美在线观看网址综合| 亚洲国产一区二区三区在线播 | 国产视频欧美视频| 欧美v日韩v国产v| 一区二区三区产品免费精品久久75 | 欧美日韩国产成人| 欧美亚洲日本国产| 亚洲欧洲日产国产综合网| 性欧美1819sex性高清| 亚洲黄色天堂| 国产精品一区二区欧美| 免费观看国产成人| 亚洲永久免费视频| 亚洲人成绝费网站色www| 久久久不卡网国产精品一区| 亚洲精品久久视频| 国产一区二区丝袜高跟鞋图片| 欧美激情区在线播放| 久久成人18免费网站| 日韩视频久久| 欧美激情一区| 久久―日本道色综合久久| 亚洲视频一起| 亚洲免费高清| 亚洲激情影院| 一色屋精品亚洲香蕉网站| 日韩视频在线观看国产| 久久精品2019中文字幕| 夜夜爽www精品| 亚洲电影在线免费观看| 久久久久久久久久久久久女国产乱| 99在线热播精品免费| 一区在线视频| 狠狠色狠狠色综合日日tαg| 国产精品免费观看视频| 欧美日韩国产一中文字不卡| 欧美sm极限捆绑bd|