现在的位置: 首页 > 综合 > 正文

uva10129

2018年01月20日 ⁄ 综合 ⁄ 共 1348字 ⁄ 字号 评论关闭
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int T, n;
int match[30][30];
int temp[30][30];
void dfs(int pos)
{
    for(int i = 0; i < 26; i++) if(temp[pos][i])
    {
        temp[pos][i] -= 1;
        dfs(i);
    }
}
int main()
{
    cin >> T;
    while(T--)
    {
        memset(match, 0, sizeof(match));
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            string in;
            cin >> in;
            match[in[0] - 'a'][in[in.size() - 1] - 'a'] += 1;
        }
        bool ok = true;
        for(int i = 0; i < 26; i++)
        {
            memcpy(temp, match, sizeof(match));
            dfs(i);
            ok = true;
            for(int i = 0; i < 30; i++)#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int T, n;
int match[30][30];
int temp[30][30];
void dfs(int pos)
{
    for(int i = 0; i < 26; i++) if(temp[pos][i])
    {
        temp[pos][i] -= 1;
        dfs(i);
    }
}
int main()
{
    cin >> T;
    while(T--)
    {
        memset(match, 0, sizeof(match));
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            string in;
            cin >> in;
            match[in[0] - 'a'][in[in.size() - 1] - 'a'] += 1;
        }
        bool ok = true;
        for(int i = 0; i < 26; i++)
        {
            memcpy(temp, match, sizeof(match));
            dfs(i);
            ok = true;
            for(int i = 0; i < 30; i++)
                for(int j = 0; j < 30; j++)
                if(temp[i][j])
                ok = false;
            if(ok) break;
        }
        if(ok)
            cout << "Ordering is possible." << endl;
        else
        cout << "The door cannot be opened." << endl;
    }
}

                for(int j = 0; j < 30; j++)
                if(temp[i][j])
                ok = false;
            if(ok) break;
        }
        if(ok)
            cout << "Ordering is possible." << endl;
        else
        cout << "The door cannot be opened." << endl;
    }
}

 

欧拉道路,给一系列的单词判断是否首尾单词相同,建立数组match用来存储26个英文字母的首尾出现次数,比如acm则match[0][13]就加一,如果可以形成欧拉道路的话则
经过dfs处理如果可以形成欧拉通路的话,则match中的数据都应该变为0,若不为0的话则无法形成欧拉道路。

【上篇】
【下篇】

抱歉!评论已关闭.