1 /*  2   这道题如果按照度为0的节点来判断的时候,将度为0的节点和其相连的节点（度数并减去1）   3   从图中去掉，如果度为0的节点的个数为0个但是图中的节点没有都去掉的   时候那么说明  4   出现了回路!用这种方法必须将重边去除掉！   5     6   所以推荐用dfs方式进行判断！这种方式还是比较直观的！   7 */  8 #include<iostream>  9 #include<cstring> 10 #include<cstdio> 11 #include<algorithm> 12 using namespace std; 13  14 int used[30]; 15 int deg[30]; 16 int map[30][30]; 17 int sum; 18 bool topoSort(){ 19     for(int i=1; i<=sum; ++i){ 20         int cnt=0, p; 21         for(int j=0; j<26; ++j) 22            if(used[j] && deg[j]==0) { 23               ++cnt; 24               p=j; 25            } 26         if(cnt==0) return false; 27         for(int j=0; j<26; ++j) 28            if(map[p][j]){ 29                map[p][j]=0; 30                --deg[j]; 31            }  32         deg[p]=-1; 33     } 34     return true; 35 } 36  37 int main(){ 38     int m; 39     char ch[5]; 40     while(cin>>m){ 41         memset(used, 0, sizeof(used)); 42         memset(deg, 0, sizeof(deg)); 43         memset(map, 0, sizeof(map)); 44         while(m--){ 45            cin>>ch;            46            used[ch[0]-‘A‘] =1; 47            used[ch[2]-‘A‘] =1; 48            if(ch[1]==‘>‘){ 49                if (map[ch[2]-‘A‘][ch[0]-‘A‘] != 1) {//去掉多重边  50                ++deg[ch[0]-‘A‘]; 51                map[ch[2]-‘A‘][ch[0]-‘A‘]=1; 52                } 53            } 54            else{ 55                if (map[ch[0]-‘A‘][ch[2]-‘A‘] != 1) { 56                ++deg[ch[2]-‘A‘]; 57                map[ch[0]-‘A‘][ch[2]-‘A‘]=1; 58             } 59           } 60         } 61         sum=0; 62         for(int i=0; i<26; ++i) 63            if(used[i])  ++sum; 64         if(topoSort()) 65            cout<<"YES"<<endl; 66         else cout<<"NO"<<endl; 67     } 68     return 0; 69 }  70  71 */ 72  73 #include<iostream> 74 #include<cstring> 75 #include<cstdio> 76 #include<algorithm> 77 using namespace std; 78 int map[30][30]; 79 int vis[30];  80  81 bool dfs(int cur){ 82     vis[cur]=-1; 83     for(int i=0; i<26; ++i) 84        if(map[cur][i]){ 85           if(vis[i]==-1) return false; 86           if(!vis[i] && !dfs(i)) return false; 87        } 88     vis[cur]=1; 89     return true; 90 } 91  92 int main(){ 93     int m; 94     char ch[5]; 95     while(cin>>m){ 96         memset(vis, 0, sizeof(vis));  97         memset(map, 0, sizeof(map)); 98         while(m--){ 99             cin>>ch;100             if(ch[1]==‘>‘)101                map[ch[2]-‘A‘][ch[0]-‘A‘]=1;102             else103                map[ch[0]-‘A‘][ch[2]-‘A‘]=1;104         }105         int flag=0;106         for(int i=0; i<26; ++i)107            if(!vis[i])108              if(!dfs(i)){109                 flag=1;110                 break;111              }112         if(flag)  cout<<"NO"<<endl;113         else cout<<"YES"<<endl; 114     }    115     return 0;116 }