1 条题解

  • 0
    @ 2026-6-12 9:46:08

    // 欧拉路径 O(nlogn)
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,cd[26],rd[26];
    vector<int> path;
    vector<string> wd; //单词
    vector<vector<pair<int,int>>> e(26); //邻接表
    int p[26]; //p[x]表示点x当前处理到第几条出边,初始值为0,相当于全局指针
    
    void dfs(int x,int id){ //x点,x点的入边编号
      for(int i=p[x]; i<e[x].size(); i=p[x]){
        p[x]=i+1;
        dfs(e[x][i].first, e[x][i].second);
      }
      if(id!=-1) path.push_back(id); //记录入边编号
    }
    int main(){
      ios::sync_with_stdio(0); cin.tie(0);
      cin>>n;
      for(int i=0; i<n; i++){
        string s; cin>>s;
        wd.emplace_back(s);
      }
      
      sort(wd.begin(),wd.end()); //单词升序
      
      for(int i=0; i<n; i++){
        int u=wd[i][0]-'a';
        int v=wd[i][wd[i].size()-1]-'a';
        e[u].push_back({v,i}); //i表示单词序
        cd[u]++; rd[v]++;
      }
      
      for(int i=0; i<26; i++)if(!e[i].empty())
        sort(e[i].begin(),e[i].end(), //对每个字母的出边按单词序排序
        [&](pair<int,int>& a,pair<int,int>& b){return a.second<b.second;}); 
    
      int cs=0,rs=0; bool ok=true; //存在欧拉路
      for(int i=0; i<26; i++){
        if(rd[i]!=cd[i]){
          if(cd[i]-rd[i]==1) cs++; //出度多1的点数
          else if(rd[i]-cd[i]==1) rs++; //入度多1的点数
          else ok=false; //度差>1,一定不存在欧拉路
        }
      }
      if(!(!cs&&!rs || cs==1&&rs==1)) ok=false; //非环非路一定不存在
    
      int start=0;
      while(!cd[start]) ++start; //找环的起点
      for(int i=0; i<26; i++)
        if(cd[i]-rd[i]==1){start=i; break;} //找路的起点
    
      dfs(start,-1); //搜索欧拉路
    
      if(path.size()!=n) ok=false; //如果不连通
        
      if(!ok) return cout<<"***\n",0;
      
      for(int i=path.size()-1; i>=0; i--){
        cout<<wd[path[i]];
        if(i) cout<<'.';
      }
      return 0;
    }
    
    • 1

    信息

    ID
    12484
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    36
    已通过
    17
    上传者