题目内容
大意：给定若干个元素的偏序关系，求是否能判定排好序后序列的顺序。
如果根据前 i 个关系可以直接得到，输出序列并直接结束程序。
如果第 i 个关系造成了矛盾，输出 i 并结束程序。
如果根据所有的关系都不能还原序列，输出无法完成。
解题思路
看到偏序关系就想到利用图论建模然后跑拓扑排序，结果30分。
说回正题：这题还是需要注意很多地方的，还是先来分析思路。
题目要求的是通过前 i 个来判断，因此我们要根据所有的关系挨个加边然后每加一次边跑一遍拓扑排序，由于 n\le26 所以不需要担心时间问题。
拓扑排序的实现有一些细节：首先显而易见的，如果给出来的偏序关系形成了环，那显然是不可以的，直接返回，判断是否有环的标准是拓扑排序能否遍历完所有给出的点，如果遍历不完，说明图存在环，直接输出矛盾即可。
但是遍历所有点并不代表就能形成完整的排序，有可能给出的是诸如下面的关系：
C
这样拓扑排序仍能遍历整张图，但是遍历的顺序不唯一，表明条件不足，所以我们要记录拓扑排序的深度 step，如果最终的深度刚好等于节点的个数才能判定排序的序列唯一。
还有要注意的就是存储入度的数组要每次重新开，不然会玄学 WA，而且这张图可能有自环与重边，所以存图的时候我使用的是 std::set，方便排除自环和重边的影响。
下面的拓扑排序函数返回值有三种：1 代表条件暂时不足，2 代表可以输出序列，0 代表出现矛盾条件。
注意 IO 的要求，防止被卡空格之类的事情出现，注意细节
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <set>
using namespace std;
set<int> g[27];//存边
set<int> all;//all是存储当前给出的所有点的集合
struct node
{
int now,step;//now为当前节点，step为拓扑排序的深度
};
int n,m,depth;
string s;
int topo()
{
s.clear();
int ind[27];//重新处理入度数组
memset(ind,0,sizeof(ind));//不memset的话会玄学
for(auto i:all)
for(auto j:g[i])
ind[j]++;//处理
queue<node> q;
int visited=0;
for(int i=1;i<=n;i++)
if((!ind[i] && all.count(i)))//既要满足入度为0，也要满足点给出过
q.push((node){i,1}),s.push_back(i+'A'-1);
while(!q.empty())
{
visited++;
int now=q.front().now,step=q.front().step;
q.pop();
for(auto i:g[now])
{
ind[i]--;
if(!ind[i])
{
q.push((node){i,step+1});
s.push_back(i+'A'-1);
depth=max(depth,step+1);
}
}
}
if(depth==n)
return 2;
if(visited<all.size())
return 0;
return 1;
}
int main()
{
scanf("%d %d",&n,&m);
if(m<n-1)//这里是一个小优化：如果给出的关系不足n-1个是铁定完不成的
{
printf("Sorted sequence cannot be determined.\n");
return 0;
}
char c[4];
for(int i=1;i<=m;i++)
{
scanf("%s",c);
int from=c[0]-'A'+1,to=c[2]-'A'+1;
g[from].insert(to);
all.insert(from),all.insert(to);
int x=topo();
if(x==0)
{
printf("Inconsistency found after %d relations.\n",i);
return 0;
}
if(x==2)
{
printf("Sorted sequence determined after %d relations: ",i);
cout<<s<<'.'<<endl;
return 0;
}
}
printf("Sorted sequence cannot be determined.\n");//如果前两种情况都没发生，那就是第三种了
return 0;
}
留言