题解 P1347 【排序】

##### 顺序是否矛盾，其实就是判断是否存在环，可以利用拓扑排序，或者Floyed。这个楼下应该讲的蛮清楚了，我就不过多赘述了。 #### 关于第二个问题如何确定顺序，其实可以将所有的X<Y看成一条从X到Y或者从Y到X的有向边，并且边权为1。然后根据之前的拓扑排序或者直接枚举一遍找出没有边指向的点也就是源点，到目前为止我们可以保证图中无环（有环的情况已经被排除）接下来就可以做一遍 _单源最长路_ 。 #### 只要存在源点到某一点的距离是n-1的那么必然这一点和源点之间存在一条路径且这条路径上刚好有n个点，根据我们定义的边就相当于找出n-1个互不重复的X<Y的条件，完全满足题目要求。 ```cpp #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int x,y,n,m,bian[30],next[2000],to[2000]; bool map[30][30],flag[30]; char s[3]; int head,tail,origin,path[30],dis[30],sum,q[10000],pre[30],len; // 队列的一些操作 bool empty() { return sum==0; } void push(int x) { tail=(tail+1)%10000; q[tail]=x; sum++; } int pop() { head=(head+1)%10000; sum--; return q[head]; } // int main() { scanf("%d%d",&n,&m); for (int t=1;t<=m;t++) { scanf("%s",s); x=s[0]-'A'+1; y=s[2]-'A'+1; flag[y]=true;//标记有边指向的点，以此找出没有边指向的点也就是源点 map[x][y]=true;//邻接矩阵存边方便Floyed next[t]=bian[x];//链式前向星存边方便找最长路 bian[x]=t; to[t]=y; for (int k=1;k<=n;k++)//Floyed找环 for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) map[i][j]=map[i][j]||(map[i][k]&&map[k][j]); for (int i=1;i<=n;i++) if (map[i][i]) {printf("Inconsistency found after %d relations.\n",t);return 0;} for (int i=1;i<=n;i++) if (!flag[i]) {origin=i;break;}//枚举找出源点 memset(dis,255,sizeof(dis));//一些基本的预处理操作 sum=1; head=-1; tail=0; q[0]=origin; dis[origin]=0; len=0;//找出正确顺序的长度 while (!empty()) { x=pop(); if (dis[x]==n-1)//找到符合要求的路径， //通过pre数组开始回退找出经过的点。 { path[++len]=x; for (int i=pre[x];i!=0;i=pre[i]) path[++len]=i; break; } for (int i=bian[x];i!=0;i=next[i]) if (dis[x]+1>dis[to[i]])//找到更长的路径，更新dis数组 { dis[to[i]]=dis[x]+1; pre[to[i]]=x; push(to[i]); } } if (len==n)//当找出的正确顺序长度等于n { printf("Sorted sequence determined after %d relations: ",t); for (int i=n;i>0;i--) printf("%c",path[i]+'A'-1); printf(".\n"); return 0; } if (len!=n&&t==m)//没找到正确顺序，并且已经读入到最后一条边了 puts("Sorted sequence cannot be determined."); } return 0; } ```