社区讨论

求助

P1347[ECNA 2001] 排序参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@lrlqd9mg
此快照首次捕获于
2024/01/20 15:10
2 年前
此快照最后确认于
2024/01/20 17:43
2 年前
查看原帖
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector> 
#include<cmath>
using namespace std;
const int N = 28;
struct Node{
	int id, val;
};
bool vis[N][N];
int kp[N];
int n, m;
int maxn, sum, exp_count, len;
vector<int> G[N];
int p[N];
void str_(){
	queue<int> q; 
	for(int i = 1; i <= 26; i++)
		for(int j = 0; j < G[i].size(); i++)
			kp[G[i][j]]++;
	for(int i = 1; i <= 26; i++)
		if(!kp[i]){
			q.push(i); 
			printf("%c", char(i+'A'));
		}
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i = 0; i < G[x].size(); i++){
			kp[G[x][i]]--;
			if(!kp[G[x][i]]){
				q.push(G[x][i]);
				printf("%c", char(G[x][i] + 'A'));
			}
		}
	}
	return ;
			
}

void tuple_(){
	queue<Node> q;
	for(int i = 1; i <= n; i++)
		if(!p[i])
			sum++, q.push({i, 0}); //入度为0点入队列 
		
	while(!q.empty()){
		int x = q.front().id;
		int now = q.front().val;
		q.pop();
		for(int i = 0; i < G[x].size(); i++){
			p[G[x][i]]--;//减入度 
			if(!p[G[x][i]]){
				sum++;
				q.push({G[x][i], now+1});
				maxn = max(now+1, maxn);
			}
		}
	}
	if(maxn == n){
		printf("Sorted sequence determined after %d relations: ", exp_count);
		str_();//构造 
		printf(".");
		exit(0);
	}
	if(sum != len){
		printf("Inconsistency found after %d relations.", exp_count);
		exit(0);//直接结束 
	}
	return ;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		char ch1, ch2;
		scanf("%c<%c", &ch1, &ch2);
		int u = ch1-'A'+1, v = ch2-'A'+1; 
		if(vis[u][v])//防止重复操作 
			continue; 
		exp_count = i;//记录当前步数 
		len += 2; //用来判断是否为环 
		sum = maxn = 0;//初始化 
		vis[u][v] = 1;//标记 
		G[u].push_back(v);
		p[u]++;//入度+1 
		tuple_();
	} 
	printf("Sorted sequence cannot be determined.");
	return 0;
}

回复

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

正在加载回复...