P1347 排序
P1347 排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列,例如,一个有序的数列A,B,C,D 表示A<B,B<C,C<D。在这道题中,我们将给你一系列形如A<B的关系,并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入输出格式
输入格式:
第一行有两个整数n,m,n表示需要排序的元素数量,2<=n<=26,第1到n个元素将用大写的A,B,C,D....表示。m表示将给出的形如A<B的关系的数量。
接下来有m行,每行有3个字符,分别为一个大写字母,一个<符号,一个大写字母,表示两个元素之间的关系。
输出格式:
若根据前x个关系即可确定这n个元素的顺序yyy..y(如ABC),输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前x个关系即发现存在矛盾(如A<B,B<C,C<A),输出
Inconsistency found after 2 relations.
若根据这m个关系无法确定这n个元素的顺序,输出
Sorted sequence cannot be determined.
(提示:确定n个元素的顺序后即可结束程序,可以不用考虑确定顺序之后出现矛盾的情况)
输入输出样例
4 6
A<B
A<C
B<C
C<D
B<D
A<B
Sorted sequence determined after 4 relations: ABCD.
3 2
A<B
B<A
Inconsistency found after 2 relations.
26 1
A<Z
Sorted sequence cannot be determined
这道题我来提供一种tarjan+拓扑排序的做法,首先我们考虑满足第二种情况的序列,如果存在矛盾,那么这个图中一定存在环,这样我们就可以用tarjan缩点判断一下是否存在环,有一点需要注意,就是如果小于号两边的数相同,那么就一定产生矛盾(非常坑)。对于第一种情况的序列,不难看出这个序列的拓扑序一定是唯一的,而且一定不存在环,也就是说每次拓扑时在栈中的元素一定只有唯一的一个,这样只需在每次拓扑开始时判断一下元素个数即可。如果第一和第二种情况均不满足,那么一定就是第三种情况咯。
最后附上代码:
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#define maxn 1005
using namespace std; struct edge
{
int next;
int to;
}g[maxn<<];
int n,m,num,col,tot,cnt,pd,cnt2,cc,pd1;
int last[maxn],de[maxn],dfn[maxn],low[maxn],co[maxn],de1[maxn];
char aa[],bb[maxn];
stack<int>s;
stack<int>ss; void add(int from,int to)
{
g[++num].next=last[from];
g[num].to=to;
last[from]=num;
} void topo()
{
for(int i=;i<=n;i++)
{
if(de1[i]==)
{
ss.push(i);
}
}
while(ss.size())
{
if(ss.size()>)//如果栈中多余一个元素,说明topo序不唯一
{
pd1=;
break;
}
int u=ss.top();ss.pop();
bb[++cc]=char(u+'A'-);
for(int i=last[u];i;i=g[i].next)
{
int v=g[i].to;
de1[v]--;
if(de1[v]==)
{
ss.push(v);
}
}
}
} void tarjan(int u)
{
dfn[u]=low[u]=++tot;
s.push(u);
for(int i=last[u];i;i=g[i].next)
{
int v=g[i].to;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!co[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
col++;cnt=;
for(;;)
{
int x=s.top();s.pop();
co[x]=col;
cnt++;
if(cnt>) pd=;//如果一个强联通分量中存在不止一个点,说明有环
if(x==u) break;
}
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%s",aa);
add(aa[]-'A'+,aa[]-'A'+);
if(aa[]-'A'+==aa[]-'A'+)
{
printf("Inconsistency found after %d relations.",i);//这里需要特判一下,不然第一个点会wa
return ;
}
de[aa[]-'A'+]++;
de1[aa[]-'A'+]=de[aa[]-'A'+];
for(int j=;j<=n;j++)
de1[j]=de[j];
tot=;col=;cc=;pd1=;
memset(co,,sizeof(co));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
while(s.size()) s.pop();
while(ss.size()) ss.pop();
for(int j=;j<=n;j++)
{
if(!dfn[j])
{
tarjan(j);//tarjan判环
}
}
if(pd==)
{
printf("Inconsistency found after %d relations.",i);
return ;
}
topo();//topo检查topo序是否唯一
if(pd1==)
{
printf("Sorted sequence determined after %d relations: ",i);
for(int j=;j<=n;j++)
{
printf("%c",bb[j]);
}
printf(".");
return ;
}
}
printf("Sorted sequence cannot be determined.");
return ;
}
最新文章
- jboss上的soap web service开发示例
- QT共享库的创建与调用(初级)(附:UI界面不能被改变的其中一个原因)
- ---Arch Linux 之AUR
- XE3随笔11:Merge、Clone、ForcePath
- PHP错误日志控制(display_errors和error_reporting)
- 次表面散射(SubSurface Scattering) Shader 【转】
- 【剑指offer】二叉树深度
- PC游戏编程(入门篇)(前言写的很不错)
- oracle_decode、case
- 学容器必须懂 bridge 网络 - 每天5分钟玩转 Docker 容器技术(32)
- BZOJ 1415: [Noi2005]聪聪和可可 [DP 概率]
- git 版本库基础知识学习
- Vim 宏
- GCD实现同步方法
- System.load()与System.loadLibrary()
- JavaWeb应用出现HTTP 500-Unable to compile class for JSP 错误 的解决
- DBCP、c3p0、Druid三大连接池区别
- OpenERP 负载平衡
- 【日志】修改redis日志路径
- PostgreSQL与MySQL的区别收集(转)