Day 4 -E - Catenyms POJ

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:

dog.gopher


gopher.rat


rat.tiger


aloha.aloha


arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,

aloha.aloha.arachnid.dog.gopher.rat.tiger

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

Input

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

Output

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

Sample Input

2

6

aloha

arachnid

dog

gopher

rat

tiger

3

oak

maple

elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger

***

思路：
可以将每个单词看作是两点一边，就变成判断欧拉路径(回路)了，从连通性和出度入度两方面判断，然后打印欧拉路径即可，代码如下(注释

int in[], out[], ans[], start, fa[], n, k;

struct edge {

    int u, v, vis;

    string s;

    bool operator<(const edge &a) const {

        return s<a.s;

    }

} Edge[];

void init() {

    memset(in, , sizeof(in)), memset(out, , sizeof(out));

    memset(ans, , sizeof(ans));

    k = ;

    for(int i = ; i <= ; ++i)

        fa[i] = i;

}

// Find-Union

int Find(int u) {

    if(fa[u] != u)

        return fa[u] = Find(fa[u]);

    return fa[u];

}

void Union(int x, int y) {

    x = Find(x), y = Find(y);

    if(x != y) fa[x] = y;

}

// judge whether connected

bool Connect() {

    int now = Find(start);

    for(int i = ; i <= ; ++i)

        if(in[i] || out[i])

            if(Find(i) != now)

                return false;

    return true;

}

// judge the in and out and set the start

bool check() {

    int t1 = , t2 = , i;

    for(i = ; i <= ; ++i) {

        if(in[i] == out[i]) continue;

        else if(in[i] == out[i] + )

            t1++;

        else if(in[i] == out[i] - ) {

            t2++;

            start = i;

        }

        else

            break;

    }

    if(i ==  && t1 == t2 && (t1 ==  || t1 == )) {

        return true;

    }

    return false;

}

//print the euler path

void dfs(int v) {

    for(int i = ; i <= n; ++i) {

        if(Edge[i].vis ==  && Edge[i].u == v) {

            Edge[i].vis = ;

            dfs(Edge[i].v);

            ans[k++] = i;

        }

    }

}

int main() {

    ios::sync_with_stdio(false);

    int T;

    cin >> T;

    while(T--) {

        cin >> n;

        init();

        for(int i = ; i <= n; ++i) {

            int u, v;

            cin >> Edge[i].s;

            u = Edge[i].s[] - 'a' + ;

            v = Edge[i].s[Edge[i].s.size()-] - 'a' + ;

            in[v]++, out[u]++;

            Edge[i].u = u, Edge[i].v = v, Edge[i].vis = ;

            Union(u, v);

        }

        sort(Edge+, Edge++n);

        start = Edge[].u;

        if(check() && Connect()) {

            dfs(start);

            for(int i = n-; i >= ; --i)

                cout << Edge[ans[i]].s << ".";

            cout << Edge[ans[]].s << "\n";

        } else {

            cout <<"***\n";

        }

    }

    return ;

}

巴特西

Day 4 -E - Catenyms POJ - 2337

最新文章

热门文章