/* NYOJ 99单词拼接: 思路：欧拉回路或者欧拉路的搜索！ 注意：是有向图的！不要当成无向图，否则在在搜索之前的判断中因为判断有无导致不必要的搜索，以致TLE! 有向图的欧拉路：abs(In[i] - Out[i])==1(入度[i] - 出度[i])的节点个数为两个 有向图的欧拉回路：所有的节点都有In[i]==Out[i] */ #include #include #include #include using namespace std;struct node{ char s[35]; int first, end;};bool cmp(node a, node b){ return strcmp(a.s, b.s) <0;}node nd[1005];int In[30], Out[30];int order[1005], vis[1005]; int n;int fun(){ memset(vis, 0, sizeof(vis)); int i; int last=-1; int first=-1; //有向图欧拉路的判断 for(i=0; i<26; ++i) { if(In[i]!=Out[i]) { //首先入度和出度之差的绝对值为 1的节点的要么没有，要么只有两个（没有欧拉回路，只有欧拉路）！ if(Out[i]-In[i]==1 && first==-1) first=i; else if(Out[i]-In[i]==-1 && last==-1) last=i; else return -1; } } if(first>-1 && last>-1) //这种情况是 欧拉路的搜索 ！ return first; else if(first==-1 && last==-1) //这种是欧拉回路的搜索！ { for(i=0; i<26; ++i) if(In[i]!=0) return i; } else return -1; }bool dfs(int st, int cnt){ if(cnt == n) return true; int ld=0, rd=n-1; while(ld<=rd){ int mid=(ld+rd)/2; if(nd[mid].first st) return false; for(int i=m; i st) return false; if(nd[i].first == st){ vis[i]=1; order[cnt]=i; if(dfs(nd[i].end, cnt+1)) return true; vis[i]=0; } } return false;}int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d", &n); memset(In, 0, sizeof(In)); memset(Out, 0, sizeof(Out)); for(int i=0; i