社区讨论
求助
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 条回复,欢迎继续交流。
正在加载回复...