30分求助
  • 板块P1347 排序
  • 楼主STUDENT00
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/25 22:51
  • 上次更新2023/10/27 09:56:03
查看原帖
30分求助
658786
STUDENT00楼主2022/9/25 22:51

这份代码样例过了,然而30

#include<bits/stdc++.h>
using namespace std;
int n,m,c[30],k,into[30],num[30],w[30][30],tt;
char a,b,d[30];
void work(int *it){
	int tot=0,ans[30]={0},into[30]={0};
	for(int i=1;i<=k;i++) into[i]=it[i];
	bool vis[30]={0};
	while(tot<k){
		int p=0,t=0;
		for(int i=1;i<=k;i++){
			if(!vis[i]&&into[i]==0){
				vis[i]=1;
				t++;
				p=i;
			}
		}
		if(!t){
			printf("Inconsistency found after %d relations.",tt);
			exit(0);
		}
		if(t==1){
			tot++;
			ans[tot]=p;
			for(int i=1;i<=num[p];i++) into[w[p][i]]--;
		}else return;
	}
	if(k==n){
		printf("Sorted sequence determined after %d relations: ",tt);
		for(int i=1;i<=n;i++) putchar(d[ans[i]]);
		putchar('.');
		exit(0);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		tt++;
		a=getchar();
		while(a<'A'||a>'Z') a=getchar();
		getchar();
		b=getchar();
		int p=a-'A',q=b-'A';
		if(!c[p]){
			k++;
			c[p]=k;
			d[k]=a;
		}
		if(!c[q]){
			k++;
			c[q]=k;
			d[k]=b;
		}
		into[c[q]]++;
		w[c[p]][++num[c[p]]]=c[q];
		work(into);
	}
	printf("Sorted sequence cannot be determined.");
	return 0;
} 
2022/9/25 22:51
加载中...