ZZUOJ 1199 大小关系(拓扑排序，两种方法_判断入度和dfs回路判断)

/*
  这道题如果按照度为0的节点来判断的时候,将度为0的节点和其相连的节点（度数并减去1）
  从图中去掉，如果度为0的节点的个数为0个但是图中的节点没有都去掉的   时候那么说明
  出现了回路!用这种方法必须将重边去除掉！ 

  所以推荐用dfs方式进行判断！这种方式还是比较直观的！
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int used[30];
int deg[30];
int map[30][30];
int sum;
bool topoSort(){
    for(int i=1; i<=sum; ++i){
        int cnt=0, p;
        for(int j=0; j<26; ++j)
           if(used[j] && deg[j]==0) {
              ++cnt;
              p=j;
           }
        if(cnt==0) return false;
        for(int j=0; j<26; ++j)
           if(map[p][j]){
               map[p][j]=0;
               --deg[j];
           }
        deg[p]=-1;
    }
    return true;
}

int main(){
    int m;
    char ch[5];
    while(cin>>m){
        memset(used, 0, sizeof(used));
        memset(deg, 0, sizeof(deg));
        memset(map, 0, sizeof(map));
        while(m--){
           cin>>ch;
           used[ch[0]-'A'] =1;
           used[ch[2]-'A'] =1;
           if(ch[1]=='>'){
               if (map[ch[2]-'A'][ch[0]-'A'] != 1) {//去掉多重边
               ++deg[ch[0]-'A'];
               map[ch[2]-'A'][ch[0]-'A']=1;
               }
           }
           else{
               if (map[ch[0]-'A'][ch[2]-'A'] != 1) {
               ++deg[ch[2]-'A'];
               map[ch[0]-'A'][ch[2]-'A']=1;
            }
          }
        }
        sum=0;
        for(int i=0; i<26; ++i)
           if(used[i])  ++sum;
        if(topoSort())
           cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
} 

*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int map[30][30];
int vis[30]; 

bool dfs(int cur){
    vis[cur]=-1;
    for(int i=0; i<26; ++i)
       if(map[cur][i]){
          if(vis[i]==-1) return false;
          if(!vis[i] && !dfs(i)) return false;
       }
    vis[cur]=1;
    return true;
}

int main(){
    int m;
    char ch[5];
    while(cin>>m){
        memset(vis, 0, sizeof(vis));
        memset(map, 0, sizeof(map));
        while(m--){
            cin>>ch;
            if(ch[1]=='>')
               map[ch[2]-'A'][ch[0]-'A']=1;
            else
               map[ch[0]-'A'][ch[2]-'A']=1;
        }
        int flag=0;
        for(int i=0; i<26; ++i)
           if(!vis[i])
             if(!dfs(i)){
                flag=1;
                break;
             }
        if(flag)  cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}