90pts 求调
  • 板块P1347 排序
  • 楼主lam_dyr
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/23 16:45
  • 上次更新2025/1/23 19:49:53
查看原帖
90pts 求调
579309
lam_dyr楼主2025/1/23 16:45

WA On Test 1

#include <bits/stdc++.h>
using namespace std;
const int N=26;
int n,m;
vector<int> g[N];
int vis[N],sz;
char seq[N];
bool flag;
bool dfs(int u){
	vis[u]=1;
	for(int v : g[u]){
		if(vis[v]==1){
			flag=1;
			return 0;
		}
		else if(vis[v]==0){
			if(!dfs(v))
				return 0;
		}
	}
	vis[u]=2;
	seq[sz++]=(char)('A'+u);
	return 1;
}
bool toposort(){
	memset(vis,0,sizeof(vis));
	sz=0;
	flag=0;
	for(int i=0;i<n;++i){
		if(vis[i]==0){
			if(!dfs(i))
				return 0;
		}
	}
	reverse(seq,seq+sz);
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		char op,u,v;
		cin>>u>>op>>v;
		if(u==v){
			cout<<"Inconsistency found after "<<i<<" relations."<<"\n";
			return 0;
		}
		g[u-'A'].push_back(v-'A');
		if(toposort()){
			if(!flag){
				bool ok=1;
				int ind[N]={0};
				int cnt=0;
				for(int j=0;j<n;++j){
					ind[j]=0;
					for(int k=0;k<n;++k){
						for(int nei : g[k]){
							if(nei==j)
								ind[j]++;
						}
					}
					if(ind[j]==0) cnt++;
				}
				if(cnt>1) ok=0;
				if(ok){
					cout<<"Sorted sequence determined after "<<i<<" relations: ";
					for(int j=0;j<sz;++j) cout<<seq[j];
					cout<<"."<<"\n";
					return 0;
				}
			}
		}
		else{
			cout<<"Inconsistency found after "<<i<<" relations."<<"\n";
			return 0;
		}
	}
	cout<<"Sorted sequence cannot be determined.";
	return 0;
} 
2025/1/23 16:45
加载中...