20分求调
  • 板块P1347 排序
  • 楼主supra
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/11 11:54
  • 上次更新2024/7/11 14:12:51
查看原帖
20分求调
1089987
supra楼主2024/7/11 11:54

测试点下载下来一样,过不了

#include<bits/stdc++.h>
using namespace std;
const int N=30;
int n,m;
int u,v;
bool vis[N];
vector<int> vec[N];
deque<int> deq;
int flr[N];
int in[N];
int tin[N];
int cnt[N];
int fl[N];
int path[N];
bool over = false;

int cti(char x){
	return x-'A'+1;
}

char itc(int x){
	return x+'A'-1;
}

int topsort(){
	memset(cnt, 0, sizeof(cnt));
	memset(fl, 0, sizeof(fl));
	for(int i=1; i<=n; i++) tin[i] = in[i];
	for(int i=1;i<=n;i++){
		if(tin[i]==0){
			deq.push_back(i);
			cnt[1]++;//cnt用于储存位于当前位次的有几个; 
			fl[i]=1;//fl储存点在第几层; 
		}//首次只有第一位的点; 
	}
	int nmb;
	nmb=0;
	while(!deq.empty()){
		int a=deq.front();
		deq.pop_front();
		path[++nmb]=a;//nmb用来正常储存输出路径; 
		for(int i:vec[a]){
			tin[i]--;
			if(tin[i]==0){
				deq.push_back(i);
				fl[i]=fl[a]+1;
				cnt[fl[i]]++;//从哪个点来,层数就从前一个加一;
			}
		}
	}
	int sumfl=0;
	for(int i=1;i<=n;i++){//先找出共有几层; 
		sumfl=max(fl[i],sumfl);
	}
	// for(int i=1;i<=sumfl;i++){
	// 	cout<< cnt[i] << ",";
	// }
	// cout << endl;
	for(int i=1;i<=sumfl;i++){
		if(cnt[i]>1) return 0;//如果有层的数量不为1,则说明有无法确定的关系; 
	}
	bool f;
	for(int i=1;i<=n;i++){
		if(tin[i]!=0) f=true;
	}
	if(f){
		return -1;
	}
	else return 1;
}

int main(){
	// ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		char a,b,c;
		cin>>a>>b>>c;
		u=cti(a),v=cti(c);
		
		vec[u].push_back(v);
		in[v]++;
		// cout << "in:";
		// for(int i=1; i<=n; i++) cout << in[i] << ",";
		// cout << endl;
		int res = topsort();
		// cout << "res:" << res << endl;
		if(res==1){
			cout<<"Sorted sequence determined after "<<i<<" relations: ";
			for(int i=1;i<=n;i++){
				cout<<itc(path[i]);
			}
			cout<<".";
			// over = true;
			return 0;
		} 
		else if(res==-1){
			cout<<"Inconsistency found after "<<i<<" relations.";
			// over = true;
			return 0;
		}
	}
	cout<<"Sorted sequence cannot be determined.";
	return 0;
}
2024/7/11 11:54
加载中...