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 <stdio.h> #include <stdlib.h> struct link { int node; struct link*next; }; struct ver { int in; struct link*next; }; int main() { int i,j,n,m,tpo,flag1,flag2,ind[26],flag[26],a,b,stack[26],tps; //n表示变量的数目,m表示关系的数目 char s[10],ord[27]; //s用来直接承接读入,ord用来记录拓扑排序 struct ver v[26]; //邻接表 struct link*p,*r; scanf("%d%d",&n,&m); while(!(n==0 && m==0)) { //读入新的一组数据时,邻接表初始化 for(i=0;i<n;i++) { v[i].in = 0; v[i].next = NULL; } getchar(); for(i=0;i<m;i++) { //读一行数据,并记录在邻接表中 gets(s); a = s[0] - 'A'; b = s[2] - 'A'; v[b].in++; if(v[a].next==NULL) { v[a].next = (struct link*)malloc(sizeof(struct link)); p = v[a].next; p->next = NULL; p->node = b; } else { p = v[a].next; while(p->next!=NULL) { p = p->next; } p->next = (struct link*)malloc(sizeof(struct link)); p = p->next; p->next = NULL; p->node = b; } //拷贝入度信息 for(j=0;j<n;j++) ind[j] = v[j].in; //拓扑排序的初始化 tpo = -1; tps = -1; for(j=0;j<n;j++) //标记点是否还在图中,1表示被移除图 flag[j] = 0; flag1 = 0; //用来标记是否有多选 for(j=0;j<n;j++) //寻找入度为0的点 { if(ind[j]==0) { stack[++tps] = j; //找到,入栈 } } if(tps>0) flag1 = 1; //拓扑排序 while(tps>=0) { //进入拓扑序列,并标记该点 ord[++tpo] = stack[tps] + 'A'; flag[stack[tps]] = 1; p = v[stack[tps]].next; tps--; //后继结点的入度都减1,并将入度为0的子节点加入到栈中 flag2 = 0; while(p!=NULL) { if(flag[p->node]==0) //如果在图中 { ind[p->node]--; if(ind[p->node]==0) { if(flag2) flag1 = 1; else flag2 = 1; stack[++tps] = p->node; } } p = p->next; } } ord[++tpo] = '\0'; if(tpo < n) { printf("Inconsistency found after %d relations.\n",i+1); break; } else if(!flag1) { printf("Sorted sequence determined after %d relations: %s.\n",i+1,ord); break; } } if(i==m) printf("Sorted sequence cannot be determined.\n"); else { for(i=i+1;i<m;i++) gets(s); } //邻接表的释放 for(i=0;i<n;i++) { p = v[i].next; if(p!=NULL) { while(p->next!=NULL) { r = p; p = p->next; free(r); } free(p); } } scanf("%d%d",&n,&m); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator