当前位置:网站首页>POJ 1094 sorting it all out
POJ 1094 sorting it all out
2022-07-06 22:33:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The question : Given a series of relationships ( Only capital letters exist ), Infer whether there is contradiction ,
Or unable to determine the relationship . Or be able to determine the only relationship
analysis : Using topological sorting . But you need to sort while entering the relationship
contradiction : Infer whether there is a ring
Determine the relationship : Can find the unique topological order
Not sure about the relationship : There is no ring , And after all the relationships are processed , The relationship is still uncertain
notes : Suppose there is a contradiction , Then there is no need to infer the next relationship
#include<stdio.h>
#include<string.h>
int n,m,vis[30],rd[30],flag[30],map[30][30],cnt;
char t[30];
int tpsort()
{
int i,j,k,num,mark=1;
cnt=0;
memset(vis,0,sizeof(vis)); // Mark whether to access
for(i=0;i<n;i++)
if(flag[i]){
num=0;
for(j=0;j<n;j++) // The calculated penetration is 0 The number of
if(flag[j]&&!rd[j]&&!vis[j])
num++;
if(num==0) // If there is no penetration, it is 0 node , Then there are rings
return 0;
if(num>1) // If the degree of penetration is 0 Node of is greater than 1. It indicates that a unique topological relationship cannot be established
mark=0;
for(j=0;j<n;j++){
if(flag[j]&&!rd[j]&&!vis[j]){
t[cnt++]=j+'A';
vis[j]=1;
break;
}
}
for(k=0;k<n;k++)
if(map[j][k])
rd[k]--;
}
if(!mark)
cnt=0;
return 1;
}
int main()
{
int i,j,mark,pos,r[30];
char s[5];
while(scanf("%d%d",&n,&m)!=EOF){
if(m==0&&n==0)
break;
mark=1;
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag)); // Mark whether the element exists
memset(r,0,sizeof(r));
for(i=1;i<=m;i++){
scanf("%s",s);
if(mark==1){
flag[s[0]-'A']=flag[s[2]-'A']=1;
if(s[1]=='>'){
map[s[2]-'A'][s[0]-'A']=1; // Record the relationship of edges
r[s[0]-'A']++; // Record the degree of penetration
}
else{
map[s[0]-'A'][s[2]-'A']=1;
r[s[2]-'A']++;
}
for(j=0;j<n;j++)
rd[j]=r[j]; // Auxiliary space . Prevent topology sorting from changing the degree of penetration in the process
mark=tpsort();
if(!mark)
pos=i;
if(mark&&cnt==n){ // When there is no ring and the relationship is certain
mark=2;
pos=i;
t[cnt]=0; // Empty characters at the end of the character array
}
}
}
if(mark==0)
printf("Inconsistency found after %d relations.\n",pos);
else if(mark==1)
printf("Sorted sequence cannot be determined.\n");
else if(mark==2)
printf("Sorted sequence determined after %d relations: %s.\n",pos,t);
}
return 0;
}
Copyright notice : This article is the original article of the blogger . Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116980.html Link to the original text :https://javaforall.cn
边栏推荐
- sizeof关键字
- 空结构体多大?
- Void keyword
- HDR image reconstruction from a single exposure using deep CNN reading notes
- Return keyword
- Attack and defense world miscall
- [linear algebra] determinant of order 1.3 n
- 每日一题:力扣:225:用队列实现栈
- [IELTS speaking] Anna's oral learning record part1
- OpenCV VideoCapture. Get() parameter details
猜你喜欢
Sword finger offer question brushing record 1
The SQL response is slow. What are your troubleshooting ideas?
每日一题:力扣:225:用队列实现栈
机试刷题1
NPDP certification | how do product managers communicate across functions / teams?
Leetcode exercise - Sword finger offer 26 Substructure of tree
云原生技术--- 容器知识点
Web APIs DOM time object
Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
Aardio - 不声明直接传float数值的方法
随机推荐
12、 Start process
labelimg的安装与使用
如何实现文字动画效果
Aardio - does not declare the method of directly passing float values
雅思口语的具体步骤和时间安排是什么样的?
柔性数组到底如何使用呢?
(18) LCD1602 experiment
2022-07-04 mysql的高性能数据库引擎stonedb在centos7.9编译及运行
Aardio - 不声明直接传float数值的方法
Dealing with the crash of QT quick project in offscreen mode
Signed and unsigned keywords
[IELTS speaking] Anna's oral learning record part1
Mise en place d'un environnement de développement OP - tee basé sur qemuv8
That's why you can't understand recursion
case 关键字后面的值有什么要求吗?
每日一题:力扣:225:用队列实现栈
云原生技术--- 容器知识点
【编译原理】做了一半的LR(0)分析器
将MySQL的表数据纯净方式导出
[leetcode] 19. Delete the penultimate node of the linked list