社区讨论

谁能help me,40pts,改对必关

P1347排序参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mlkcjhu3
此快照首次捕获于
2026/02/13 11:47
6 天前
此快照最后确认于
2026/02/15 23:20
4 天前
查看原帖
40pts:
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m,q[30][30],d[30],p[30],sum,flag,a,b;
string s;
queue<int> ans;
void bfs(){
	while(ans.size()){
		ans.pop();
	}
	queue<int> s;
	for(int i = 1;i<=n;i++){
		if(d[i] == 0){
			s.push(i);
		}
	}
	while(!s.empty()){
		sum++;
		int si = s.size();
		
		if(si>1){
			flag = 0;
			return;
		}
		int top = s.front();
		ans.push(top);
		s.pop();
		for(int i = 1;i<=n;i++){
			if(q[top][i]==1){
				if(--d[i]==0){
					s.push(i);
					
				}
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		
		cin>>s;
		a = s[0] - 'A'+1;
		b = s[2] - 'A'+1;
		if(q[b][a]==1){
			printf("Inconsistency found after %d relations.",i);
			return 0;
		}
		
		if(q[a][b]!=1){
			p[b] ++;
		}
		q[a][b] = 1;
		for(int j = 1;j<=n;j++){
			d[j] = p[j];
		}
		sum = 0;
		flag = 1;
		bfs();
		if(flag&&sum==n){
			printf("Sorted sequence determined after %d relations: ",i);
			while(ans.size()){
				cout<<char(ans.front()+'A'-1);
				ans.pop();
			}
			printf(".");
			return 0;
		}
	}
	cout<<"Sorted sequence cannot be determined.";
	
	
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...