UVa 200 Rare Order

 1  #include<stdio.h>

 2  #include<stdlib.h>

 3  #include<iostream>

 4  #include<algorithm>

 5  #include<map>

 6  using namespace std;

 7  bool adj[30][30];

 8  map<char,int> ma;

 9  map<int,char> re;

10  int ind=0,idx=1;

11  void com(string str1,string str2)

12  {

13      int len1=0,len2=0;

14      len1=str1.length(),len2=str2.length();

15      for(int i=0,j=0; i<len1 && j<len2 ; i++,j++)

16      {

17          if(str1[i]!=str2[j])

18          {

19              adj[ma[str1[i]]][ma[str2[j]]]=true;

20              break;

21          }

22      }

23  }

24  int vis[30]={0};

25  int topo[30]={0},t;

26  bool dfs(int u,int n)

27  {

28      vis[u]=-1;

29      for(int v=1;v<=n;v++)

30      {

31          if(adj[u][v]==true)

32          {

33              if(vis[v]<0) return false;

34              else if(!vis[v]&&!dfs(v,n)) return false;

35          }

36      }

37      vis[u]=1;

38      topo[--t]=u;

39      return true;

40  }

41  bool toposort(int n)

42  {

43      t=n;

44      for(int u=1;u<=n;u++) if(!vis[u] && !dfs(u,n)) return false;

45      return true;

46  }

47  int main()

48  {

49      string str[100000];

50      while(cin>>str[ind])

51      {

52          if(str[ind][0]=='#') break;

53          int len=str[ind].length();

54          for(int i=0;i<len;i++)

55          {

56              if(ma[str[ind][i]]==0)

57              {

58                  ma[str[ind][i]]=idx;

59                  re[idx]=str[ind][i];

60                  idx+=1;

61              }

62          }

63          ind++;

64      }

65      for(int i=0; i<ind-1; i++)

66      {

67          com(str[i],str[i+1]);

68      }

69      toposort(idx-1);

70      for(int i=0;i<idx-1;i++)

71      {

72        cout<<re[topo[i]];

73      }

74      cout<<endl;

75      return 0;

76  }