poj1135 - Domino Effect

                             想看更多的解题报告:http://blog.csdn.net/wangjian8006/article/details/7870410

                              转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意:给出一些边,有向的,判断是否可以得出顺序

而且是一个边一个边加上去判断

如果可以得到所有顶点的顺序就输出顺序并且是在第几个边加进来时

有可能加入这个顶点的时候得到一个环那么就判断矛盾了

当所有的顶点加进来也不可以就判断不可以排序

一个拓扑排序后就可以找出顺序与有没有有向环

代码写的比较浪

#include "stdio.h"
#include "stdlib.h"

#define MAXV 1000

typedef struct adlist{
	int endegree;		//入度
	char vertiem;		//结点值
	struct adlist *next;	//下一个节点
	bool flag;    //拓扑排序时用来判断是否被发现
}verhead;

int vsum;				//顶点总数
verhead *node[MAXV];		//邻接表用全局变量存
int vlin;				//找到那一个入度为零的点
int eng[MAXV];    //新开一个数组来计算拓扑排序中的入度
int lujing[MAXV];	//记录路径

bool discover(char x);  //用来计算此结点是否出现过
void newnode(char x);  //开辟一个新的结点空间存放
void delist(char n,char m); //连入邻接表
bool topsort(int n,int to);    //拓扑排序
bool tflin();			//判断在没有发现的结点里是否有唯一零

int main(){
	int i,n,m,flag;
	char x[1000],y[1000];

	verhead *q;
	while (1){
		scanf("%d %d\n",&n,&m);
		if(n==0 && m==0) break;
		vsum=0;flag=0;
		for(i=1;i<=m;i++) 
			scanf("%c<%c\n",&x[i],&y[i]);
		
		for(i=1;i<=m;i++){
			if(!discover(x[i])) newnode(x[i]);
			if(!discover(y[i])) newnode(y[i]);//如果没发现则开辟一个新的结点空间存放
			delist(x[i],y[i]);				//将x->y的连入邻接表
			if (topsort(n,i)){		//判断有没有环和唯一路径
				flag=1;
				break;
			}
		}

		if(flag==0) printf("Sorted sequence cannot be determined.\n");
	}
	return 0;
}

bool discover(char x){
	int i;
	for(i=0;i<vsum;i++) if(x==node[i]->vertiem) return true;
	
	return false;
}

void newnode(char x){
	node[vsum]=(verhead *)malloc(sizeof(verhead));
	node[vsum]->vertiem=x;
	node[vsum]->next=NULL;
	node[vsum]->endegree=0;
	node[vsum]->flag=false;
	vsum++;      //总结点数加1
}

void delist(char n,char m){
	int i;
	verhead *q,*p;
	
	for(i=0;i<vsum;i++){   //在结点数组中找到n这一点
		if(node[i]->vertiem==n) break;
	}
	//在n结点的后面插入m
	q=node[i];
	while(q->next!=NULL){
		q=q->next;
		if (q->vertiem==m) return;
	}
	p=(verhead *)malloc(sizeof(verhead));
	p->next=NULL;
	p->vertiem=m;
	q->next=p;
	//找到m结点，使它的入度加1
	for(i=0;i<vsum;i++){
		if(node[i]->vertiem==m){
			node[i]->endegree++;
			break;
		}
	}
}

bool topsort(int n,int to){
	int i;
	int t;			//记录路径有几个数了
	int flag;		//用来判断排序是否唯一
	verhead *q;
	
	flag=0;t=0;
	for(i=0;i<vsum;i++){
		eng[i]=node[i]->endegree;
		lujing[i]=-1;	//初始化路径值
		node[i]->flag=false;
	}
	
	while(1){
		for(i=0;i<vsum;i++)
			if(node[i]->flag==false && eng[i]==0) break;
		if(i==vsum) break;
		if(!tflin()) flag=1;		//判断在没有发现的结点里是否有唯一零
		lujing[t++]=i;
		node[i]->flag=true;
		q=node[i];
		while(q->next!=NULL){
			q=q->next;
			for(i=0;i<vsum;i++) 
				if(node[i]->vertiem==q->vertiem){
					eng[i]--;
					break;
				}
		}
	}	
	for(i=0;i<vsum;i++)		//判断有无环
		if(eng[i]!=0){
			printf("Inconsistency found after %d relations.\n",to);
			return true;
		}
	if (flag==0 && vsum==n){			//判断有无唯一路径
		printf("Sorted sequence determined after %d relations: ",to);
		for(i=0;i<vsum;i++) printf("%c",node[lujing[i]]->vertiem);
		printf(".\n");
		return true;
	}
	return false;
}

bool tflin(){
	int i,lin;
	lin=0;
	for(i=0;i<vsum;i++)
		if (node[i]->flag==false  && eng[i]==0) lin++;
	if(lin==1) return true;
	else return false;
}