玄关!!!
  • 板块P1347 排序
  • 楼主20130709aaa
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/7 14:24
  • 上次更新2024/7/7 16:29:05
查看原帖
玄关!!!
1264264
20130709aaa楼主2024/7/7 14:24

蒟蒻最后一个过不了,求调,谢谢巨佬!

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,num;
vector<int> vec[105];
int rudu[105],a[105];
bool st[105];
int get(char ch){
    return ch-'A';}
bool topo(int r){
    queue<int>q;
    int num=0;
    bool flag=1;
    int t[105];
       for(int i=0;i<n;i++){
        t[i]=rudu[i];
        if(!rudu[i]){
			q.push(i);
			st[i]=1;}}
    while(q.size()){
	    if(q.size()>1){
			flag=0;}
	    int k=q.front();
        a[num++]=k;
        q.pop();
        for(int i=0;i<vec[k].size();i++){
			t[vec[k][i]]--;}
        for(int i=0;i<n;i++){
            if(!t[i]&&!st[i]){
				q.push(i);
				st[i]=1;}}}
    if(num < n){return 0;}
    if(flag&&!ans){ans=r;}
    return 1;}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        char c[3];
        cin>>c[0]>>c[1]>>c[2];
        int x=get(c[0]),y=get(c[2]);
        vec[x].push_back(y);
        rudu[y]++;
        if(!topo(i)){
            cout<<"Inconsistency found after "<<i<<" relations.";
            return 0;}
        memset(st,false,sizeof st);}
    if(ans){
        cout<<"Sorted sequence determined after "<<ans<<" relations: ";
        for(int i=0;i<n;i++)
			cout<<char(a[i]+'A');
        cout<<".";}
    else{cout<<"Sorted sequence cannot be determined.";}
    return 0;}

qwq

2024/7/7 14:24
加载中...