| ||||||||||
| 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