Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这道题还是老老实实地用拓扑排序最好

Posted by lizimeng at 2016-01-02 13:27:55 on Problem 1094
表示自己想的算法后来发现不对,然后改了一天最后还是用了拓扑排序。
附上代码:
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator