후행 문자 연결에 대한 문자열 순열

Question

나는 컴퓨터 과학/수학에 대해 배우기 위해 고등학생을위한 게임을 쓰고 있습니다.

그러나 나는 나 자신을 위해 설계 한 질문에 갇혀 있으며, 문제를 해결할 더 효율적인 방법이 있는지 알고 싶습니다.

질문 :

가 [..., "고양이", "틱", "사과", "오렌지"] 단어 "ABC"와 단어의 목록을 제공 는 것이 가능을 구성하는 것입니다 첫 번째 단어의 마지막 문자가 단어 목록에서 선택된 단어의 첫 번째 문자와 동일한이 조건에서 단어 체인. 그리고이 사슬은 주어진 단어 목록에 의해 성공적으로 구성 될 수 있습니까? 가능한 경우는 true를, 가능한 경우는 false를 돌려줍니다. 예를 들어

INPUT: boolean lastCharPermutation(String startingWord, String [] wordsList) { .. } 

OUTPUT: true for able to complete the combination, false otherwise 

,

사례 # 1 : 사실 2 케이스 #

Abc-Cat-Tick-King-Good-Dog-Girl 때문에 가 "Abc", ["Girl", "King", "Cat", "Dog", "Good", "Tick"] 돌아 보자 이 "Abc", ["Tour", "Game", "Cat", "Bridge", "Women", "Man"] 반환 거짓을 가지고 becau 자체 Abc-Cat-Tour하고 싶은 것은 Eulerian Path 거기

Answer 1

정지 .. 나는 Codechef에서 같은 문제를 해결했다. 당신이 사용하고자하는 경우 이것은 내 코드입니다. Plz는 설명이 필요한지 말해 주지만 이해하기는 매우 쉽습니다.

#include <iostream> 
#include <string.h> 
#include <string> 
using namespace std; 

int visit[26]; 
int adj[26][26]; 
int count=0; 

void scc(int i) //Strongly COnnected Component 
{ 
    visit[i]=-1;//visiting 
    for(int t=0;t<26;t++) 
    { 
     if(adj[i][t]>0 && visit[t]==0)//not visited yet 
     scc(t); 
    } 
    visit[i]=1; 
    count++; 
} 

int main() 
{ 
    string in; 
    int t,n,k,nv,counta,countb,flag; 
    int a[26],b[26]; 
    cin >> t; 
    while(t--) 
    { 
     cin >> n; 
     memset(a,0,26*sizeof(int)); 
     memset(b,0,26*sizeof(int)); 
     memset(visit,0,26*sizeof(int)); 
     memset(adj,0,26*26*sizeof(int)); 
     k=26;count=0;counta=0;countb=0;flag=0;nv=0; 

     while(n > 0) 
     { 
      n--; 
      cin >> in; 
      a[in[0]-'a']++; 
      b[in[in.size()-1]-'a']++; 
      adj[in[0]-'a'][in[in.size()-1]-'a'] = 1; 
      adj[in[in.size()-1]-'a'][in[0]-'a'] = 1; 
     } 

     for(int i=0;i<26;i++) 
      if(a[i]>0) 
      { 
       scc(i); 
       break; 
      } 

     for(int i=0;i<26;i++) 
      if(a[i]!=0 || b[i]!=0) 
       nv++; 

     if(count!=nv) 
      flag=1;  

     while(k > 0 && flag!=1 ) 
     { 
      if(a[k-1]-b[k-1] == 1) 
       counta++; 
      else if(b[k-1]-a[k-1] == 1) 
       countb++; 
      else if(a[k-1]!=b[k-1]) 
       flag = 1; 
      k--; 
     } 

     if(flag==0 && counta==countb && (counta==1 || counta ==0)) 
      cout << "Ordering is possible." <<endl; 
     else 
      cout << "The door cannot be opened." <<endl; 
    } 

    return 0; 
}