前言
这道题是拓扑排序判环乱搞的模板题,但有不少坑点,简单难度似乎有点低
前置芝士
拓扑排序判环
算法1
(拓扑排序判环) $O(m*(m+n))$
这道题数据很小,直接暴力就可以了,暴力枚举前$num$条边,数据小到连图都不用建,如果拓扑排序序列唯一,就是可以确定了,输出就好了,如果有环就说明有冲突,否则就是还无法确定
注意有几个坑点
- 1.输出的句子要注意$.$,空格等,一定要仔细
- 2.一定要先判环,不要发现拓扑排序序列不唯一就返回
时间复杂度
$O(m*(m+n))$
C++ 代码
希望可以自己写,我写的不大好,仅供参考
#include<bits/stdc++.h>
using namespace std;
const int N=3000;
queue<int> q;
int n,m,i,ru[N],cx[N],x[N],y[N],ans[N],len;
bool visit[N],flag,over,ovvv;
char str[3];
void pd(int num)
{
int i,xxx;
memset(visit,false,sizeof(visit));
memset(ru,0,sizeof(ru));
len=0; ovvv=false;
while (!q.empty()) q.pop();
for (i=1;i<=num;i++) ru[y[i]]++;
flag=false;
for (i=1;i<=n;i++)
if (!ru[i])
{
visit[i]=true;
q.push(i);
if (!flag)//flag标记一层中入度为0的点是否唯一,确定序列是否唯一
{
flag=true;
len++;
ans[len]=i;
} else ovvv=true;
}
while (q.size())
{
xxx=q.front();
flag=false;
for (i=1;i<=num;i++)
if (x[i]==xxx)
{
ru[y[i]]--;
if (!ru[y[i]])
{
visit[y[i]]=true;
q.push(y[i]);
if (!flag)
{
flag=true;
len++;
ans[len]=y[i];
}
else ovvv=true;
}
}
q.pop();
}
for (i=1;i<=n;i++)
if ((!visit[i])&&cx[i])
{
cout<<"Inconsistency found after "<<num<<" relations."<<endl;
over=true;
return;
}//先判环
if (ovvv) return;//再判能不能确定
for (i=1;i<=n;i++)
if (!visit[i]) return;
cout<<"Sorted sequence determined after "<<num<<" relations: ";
over=true;
for (i=1;i<=len;i++)
cout<<(char)(ans[i]+64);
cout<<'.'<<endl;//注意不能少
}
int main()
{
while (1)
{
cin>>n>>m;
if (n==0&&m==0) break;
for (i=1;i<=m;i++)
{
cin>>str;
x[i]=str[0]-'A'+1;
y[i]=str[2]-'A'+1;
}
memset(cx,0,sizeof(cx));
over=false;
for (i=1;i<=m;i++)//暴力枚举
{
cx[x[i]]=true;
cx[y[i]]=true;//标记出现的点
pd(i);
if (over) break;
}
if (!over) cout<<"Sorted sequence cannot be determined."<<endl;
}
}
可以再加点注释
很不错啊