UVa 10129 Play on Words

 1  #include <stdio.h>

 2  #include <stdlib.h>

 3  #include <iostream>

 4  #include <algorithm>

 5  #include <string.h>

 6  #include <vector>

 7  using namespace std;

 8  typedef pair<int,int> ii;

 9  int adj[30][30]= {0};

10  int out[30]= {0},in[30]= {0};

11  vector<ii> edges;

12  int E=0;

13  void Findeuler(int start)

14  {

15      for(int i=0; i<26; i++)

16      {

17          if(adj[start][i]>0)

18          {

19              adj[start][i]--;

20              Findeuler(i);

21              edges.push_back(ii(start,i));

22          }

23      }

24  }

25  bool euler(int n)

26  {

27      int point1=0,point2=0,startp=-1,endp=-1;

28      bool flag=true;

29      for(int i=0; i<26; i++)

30      {

31          if(out[i]-in[i]==1) point1++,startp=i;//start

32          else if(in[i]-out[i]==1) point2++,endp=i;//end

33          else if(out[i]!=in[i])

34          {

35              flag=false;

36              break;

37          }

38      }

39      if(!(flag==true && ((point1==1 && point2 ==1)||(point1==0 && point2 ==0))))

40      {

41 

42          return false;

43      }

44      else

45      {

46          if(startp!=-1)

47          {

48              edges.clear();

49              Findeuler(startp);

50              if(edges.size()==E) return true;

51              else return false;

52 

53          }

54          else

55          {

56              for(int i=0; i<26; i++)

57              {

58                  edges.clear();

59                  if(out[i]!=0) Findeuler(i);

60                  if(edges.size()==E) return true;

61              }

62              return false;

63          }

64      }

65  }

66  int main()

67  {

68      int cas;

69      cin>>cas;

70      while(cas--)

71      {

72          int n;

73          cin>>n;

74          E=0;

75          memset(adj,0,sizeof(adj));

76          memset(out,0,sizeof(out));

77          memset(in,0,sizeof(in));

78          for(int i=0; i<n; i++)

79          {

80              string str;

81              cin>>str;

82              adj[str[0]-'a'][str[str.length()-1]-'a']+=1;

83              out[str[0]-'a']+=1;

84              in[str[str.length()-1]-'a']+=1;

85              E++;

86          }

87          if(euler(n)) printf("Ordering is possible.\n");

88          else printf("The door cannot be opened.\n");

89      }

90      return 0;

91  }