ZZUOJ 1199 大小关系(拓扑排序，两种方法_判断入度和dfs回路判断)
生活随笔
收集整理的這篇文章主要介紹了
ZZUOJ 1199 大小关系(拓扑排序，两种方法_判断入度和dfs回路判断)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1 /*
2 這道題如果按照度為0的節(jié)點來判斷的時候,將度為0的節(jié)點和其相連的節(jié)點（度數(shù)并減去1）
3 從圖中去掉，如果度為0的節(jié)點的個數(shù)為0個但是圖中的節(jié)點沒有都去掉的 時候那么說明
4 出現(xiàn)了回路!用這種方法必須將重邊去除掉！
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 else
103 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 }
?
轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3911559.html
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎總結(jié)
以上是生活随笔為你收集整理的ZZUOJ 1199 大小关系(拓扑排序，两种方法_判断入度和dfs回路判断)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 那个设置是usb启动怎么办 usb启动设
- 下一篇： 怎么破解电脑管理员密码 如何突破电脑管理