列表

详情

NC51247. Sorting It All Out

描述

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

输入描述

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where . The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

输出描述

For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

示例1

输入: 

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

输出: 

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 380K, 提交时间: 2020-08-21 15:00:32 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn=1e3+10;

int n,m;
vector<int> g[35];
string s;
int deg[35],d[35];
string ans;

int topsort(){
	ans.clear();
	memcpy(d,deg,sizeof deg);
	queue<int> q;
	bool f=1;
	int cnt=0;
	for(int i=1;i<=n;i++) if(d[i]==0) q.push(i);
	while(!q.empty()){
		if(q.size()>1) f=0;
		int u=q.front();
		ans=char(u+'A'-1)+ans;
		q.pop();
		cnt++;
		for(int i=0;i<g[u].size();i++){
			int j=g[u][i];
			d[j]--;
			if(d[j]==0) q.push(j); 
		}
	}
	if(cnt==n){
		if(f) return 1;
		return 2;
	}
	return 3;
}

int main(){
	while(cin>>n>>m){
		if(n==0&&m==0) return 0;
		for(int i=0;i<=n;i++){
			g[i].clear();	
			deg[i]=0;
		}
		int u,v,f=2,xb;
		for(int i=1;i<=m;i++){
			cin>>s;
			if(f==1||f==3) continue;
			u=s[2]-'A'+1;
			v=s[0]-'A'+1;
			deg[v]++;
			g[u].push_back(v);
			f=topsort();
			if(f==1||f==3) xb=i;
		}
		if(f==1) cout<<"Sorted sequence determined after "<<xb<<" relations: "<<ans<<"."<<endl;
		else if(f==2) cout<<"Sorted sequence cannot be determined."<<endl;
		else if(f==3) cout<<"Inconsistency found after "<<xb<<" relations."<<endl;
	}
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 29ms, 内存消耗: 472K, 提交时间: 2020-05-02 20:55:27 

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[50][50],b[50][50];
int floyd() {
	memcpy(b,a,sizeof(b));
	for(int k=0;k<n; k++)
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++) {
				b[i][j]|=b[i][k]&&b[k][j];
				if(b[i][j]==b[j][i]&&b[i][j]&&i!=j)return -1;
			}
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			if(b[i][j]==b[j][i]&&!b[i][j]&&i!=j)return 0;
	return 1;
}
void solve() {
	char s[20];
	int f=0;
	memset(a,0,sizeof(a));
	for(int i=0; i<m; i++) {
		scanf("%s",s);
		a[s[0]-'A'][s[2]-'A']=1;
		int now=floyd();
		if(f)continue;
		if(now==-1) {
			f++;
			printf("Inconsistency found after %d relations.\n",i+1);
		} else if(now==1) {
			f++;
			printf("Sorted sequence determined after %d relations: ",i+1);
			vector<pair<int,char> > ve(n);
			for(int j=0; j<n; j++) {
				ve[j].first=0;
				ve[j].second=j+'A';
			}
			for(int k=0; k<n; k++)
				for(int j=0; j<n; j++)
					ve[k].first+=b[k][j];
			sort(ve.begin(),ve.end());
			for(int i=n-1; i>=0; i--)
				cout<<ve[i].second;
			puts(".");
		}
	}
	if(!f)puts("Sorted sequence cannot be determined.");
}
int main() {
	while(cin>>n>>m&&(n||m))solve() ;
	return 0;
}

上一题

© 2024 nowcoder.com