Intermediate.
Put your skills to the test.

Problem summary

Build the longest chain of supplied words such that each next word begins with the last letter of the previous word. A word can be used once. The statement guarantees that a matching next word, when one exists, is unique. Break equal-length ties by the alphabetically smallest first word. Print 0 if no pair of words can be linked.

Source clarification. The source does not explicitly define a length-one chain or the alphabet beyond its examples. We follow its “no matching words → 0” instruction and ordinary lexicographic ordering of the supplied Latin words. The unique-successor promise is essential.

Constraints

1 ≤ N ≤ 26; each word has at most 10 letters.

Worked example

Original statement sample.

5
bear
new
door
sky
word

3
new
word
door

Solution analysis

1. Try every word as the first word. Because the next word is unique, there is no branching choice after that starting point. Search the input for an unused word beginning with the current word’s last letter.
2. Keep a used array for this particular attempt. Stop when no unused successor exists. This also stops a cycle: returning to a previously used word is forbidden. Compare the resulting chain with the best by length and then by its first word.
3. For the sample, starting from new produces new → word → door. Starting from word gives only word → door, and bear and sky cannot extend the best chain. The chosen length is therefore 3.

Why it works

Every valid chain has a supplied first word. For a fixed first word, the unique-successor promise forces every subsequent usable word; stopping at a missing or already used successor is necessary. Trying all first words therefore includes a longest chain, and the comparison applies the required tie-break.

Watch out. Reset the used array for every starting word. Do not reuse words around a cycle. The source says to output 0 when no words satisfy the linking condition; this implementation treats a single isolated word as no chain.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<string>words(n);
    for(string&word:words){
        cin>>word;
    }
    vector<int>best;
    for(int start=0;start<n;start++){
        vector<bool>used(n,false);
        vector<int>chain;
        int current=start;
        while(current!=-1){
            chain.push_back(current);
            used[current]=true;
            int next=-1;
            for(int candidate=0;candidate<n;candidate++){
                if(!used[candidate]&&words[candidate].front()==words[current].back()){
                    next=candidate;
                    break;
                }
            }
            current=next;
        }
        // With unique successors, only the first word breaks equal-length ties.
        if(chain.size()>best.size()||
            (chain.size()==best.size()&&words[start]<words[best.front()])){
            best=chain;
        }
    }
    if(best.size()<2){
        cout<<0<<'\n';
        return 0;
    }
    cout<<best.size()<<'\n';
    for(int index:best){
        cout<<words[index]<<'\n';
    }
}