Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
亲爱的同道中人进来看看!#include<iostream> //POJ 1094 using namespace std; #define SIZE 30 bool map[SIZE][SIZE],ok,in[SIZE]; int degree[SIZE]; char out[SIZE]; int stack[SIZE],f; bool toposort(int n) { ok = true; int c = 0,i; f = 0; int temp[SIZE]; for(i = 1; i <= n; i++) temp[i] = degree[i]; memset(in,0,sizeof(in)); for(i = 1; i <= n; i++) if(!temp[i]){ in[i] = true; stack[++f] = i; } while(f != 0){ if(f > 1) ok = false; //? int e = stack[f--]; out[c++] = e+'A'-1; for(i = 1; i <= n; i++) if(map[e][i]){ if(!(--temp[i])){ in[i] = true; stack[++f] = i; } } } out[c] = '\0'; if(c < n) return false; else return true; } int main() { int n,k,i,p; char a,b,r; while(cin >> n >> k && n+k){ memset(map,0,sizeof(map)); memset(degree,0,sizeof(degree)); bool over = false; bool diff = false; for(i = 1; i <= k; i++){ cin >> a >> r >> b; map[a-'A'+1][b-'A'+1] = true; degree[b-'A'+1]++; if(!over){ bool t =toposort(n) ; if(t && ok){ over = true; p = i; } else if(!t){ over = true; diff = true; p = i; } } } if(over && ok && !diff) cout << "Sorted sequence determined after "<<p<< " relations: "<<out<<"."<<endl; else if(over && diff) cout << "Inconsistency found after "<<p<<" relations."<<endl; else cout << "Sorted sequence cannot be determined." << endl; } return 0; } while(f != 0){ if(f > 1) ok = false; //这句有什么用 我一直没搞懂!如果去掉它又该怎么来写该题代码,?非常感谢你的回答! Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator