Poj 1094 Sorting It All Out (传递闭包+拓扑排序)

港控/mmm° 2022-11-15 14:06 48阅读 0赞

题意：给你一些大写字母间的大小排序关系，判断以下3中情况：1 能唯一确定它们的排列顺序，2 所给关系是矛盾的，3 到最后也不能确定它们之间的关系。

思路：出现矛盾也就是在比较大小关系的过程中出现环，可以通过Floyd算法求传递闭包来判环。

如果没有环且每个点的出度+入度==n-1，则表明字母之间两两关系确定，构成唯一的一个序列，存在答案，否则不存在。

当答案存在时，利用拓扑排序确定各点顺序。

简单说一下拓扑排序，以下摘自http://blog.csdn.net/midgard/article/details/4101025：

拓扑排序是对有向无环图(DAG图)的一种排序。表示了顶点按边的方向出现的先后顺序。如果有环，则无法表示两个顶点的先后顺序。

在现实生活中，也会有不少应用例子，比如学校课程布置图，要先修完一些基础课，才可以继续修专业课。

一个简单的求拓扑排序的算法：首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑排序。

代码写法参考了：http://www.cppblog.com/infinity/archive/2008/11/06/66086.html

#include <cstdio>
    #include <cstring>
    
    int n,m;
    int indegree[30],outdegree[30],stack[30];
    bool map[30][30],visit[30];
    char str[30],ch[10];
    
    bool Floyd ()
    {
    	int i;
    	for (i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++)
    		if (map[j][i] && map[i][k])
    			map[j][k]=true;
    	for (i=0;i<n;i++)
    		if (map[i][i])
    			return false;   //自己与自己连通说明出现环
    	return true;
    }
    
    bool Cal ()
    {
    	memset(indegree,0,sizeof(indegree));
    	memset(outdegree,0,sizeof(outdegree));
    	int i,j;
    	for (i=0;i<n;i++) for (j=0;j<n;j++)
    		if (map[i][j])
    			indegree[j]++,outdegree[i]++;
    	for (i=0;i<n;i++)
    		if (indegree[i]+outdegree[i]!=n-1)
    			return false;
    	return true; //所有点出度入度之和均为n-1则说明所有关系确定
    }
    
    void toplogical_sort ()
    {
    	int i,id=0,top=1;
    	for (i=0; i<n;i++)
    		if (indegree[i]==0)
    		{
    			stack[1]=i;
    			break;
    		}
    	memset (visit,false,sizeof(visit));
    	while (top)
    	{
    		int cur=stack[top--];  //当前正在处理地入度为0的节点
    		visit[cur]=true;
    		str[id++]=cur+'A';
    		for (i=0;i<n;i++)
    		{
    			if (visit[i]==false && map[cur][i]) indegree[i]--;  //将所有子节点的入度-1
    			if (i!=cur && visit[i]==false && indegree[i]==0) stack[++top]=i;
    		}
    	}
    	str[id]='\0';
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	while (scanf("%d%d",&n,&m),n)
    	{
    		memset(map,false,sizeof(map));
    		int flag1=0; //标记矛盾出现时的步数
    		int flag2=0; //标记相互关系已经确认的步数
    		for (int i=1;i<=m;i++)
    		{
    			scanf("%s",ch);
    			map[ch[0]-'A'][ch[2]-'A']=true;
    			if (flag1 || flag2) continue;
    			else if (Floyd()==false)
    			{
    				flag1=i;
    				continue;
    			}
    			else if (Cal())
    			{
    				toplogical_sort ();
    				flag2=i;
    			}
    		}
    		if (flag1) printf("Inconsistency found after %d relations.\n",flag1);
    		else if (flag2) printf("Sorted sequence determined after %d relations: %s.\n",flag2,str);
    		else printf("Sorted sequence cannot be determined.\n");
    	}
    	return 0;
    }