A - Dictionary

传送门

题目大意

给你n个字符串，问是否可以通过改变26个字母的排列顺序是这n个字符串的字典序是非降排列的。

分析

我们考虑设相邻两个字符串的第一个不相同字符的位置为j，以为要求字典序不降，所以有第i个字符串的第j位向第i+1个字符串的第j位连边，最后如果没有环则代表可以找到一种顺序，反之不能。

注：代码应用的是floyd判环。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define sp cout<<"---------------------------------------------------"<<endl

#define pb push_back

char s[][];

int g[][],ok;

int main(){

      int n,m,i,j,k;

      scanf("%d",&n);

      while(n!=){

          ok=;

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

            scanf("%s",s[i]);

          memset(g,,sizeof(g));

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

            int len=strlen(s[i]),len2=strlen(s[i+]);

            j=;

            while(j<len&&j<len2&&s[i][j]==s[i+][j])j++;

            if(j<len&&j==len2){

                ok=;

                break;

            }

          if(j<len&&j<len2){

            g[s[i][j]-'a'][s[i+][j]-'a']=;

          }

        }

        for(k=;k<;k++)

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

            for(j=;j<;j++)

              g[i][j]|=(g[i][k]&g[k][j]);

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

          if(g[i][i])

            ok=;

        if(ok)puts("yes");

          else puts("no");

        scanf("%d",&n);

      }

      return ;

}