posts - 33,  comments - 33,  trackbacks - 0
题意:如果单词A的结尾字母与单词B的首字母相同,那么可以认为是A到B相通。给出一系列单词,求这些词按照某种排列能否串通。
题解:
如果直接按照题意建模,以单词为顶点,边表示两两相通,那么将会得到哈密顿回路模型。显然是很难解的。
换一种方式,以字母为顶点,边表示传送的单词,那么就得到欧拉回路模型的图,可以按照欧拉定理求解。
以下给出Euler图的相关知识:
Euler回路:G中经过每条边一次且仅一次的回路
Euler路径:G中经过每条边一次且仅一次的路径
无向图存在Euler回路定理:当它是连通图+顶点度数为偶数
无向图存在Euler路径定理:当它是连通图+除两个顶点度为奇数外,其余为偶数
有向图存在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 阅读(1534) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理