WA20 求调
  • 板块P1347 排序
  • 楼主llqqhh
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/2 15:06
  • 上次更新2024/3/2 17:11:00
查看原帖
WA20 求调
525817
llqqhh楼主2024/3/2 15:06

下载了#2的数据,本地跑过了,洛谷IDE也过了, 提交时就WA

input :

4 6
C<D
C<B
B<A
C<D
D<A
A<A

expected output:

Inconsistency found after 6 relations.

code:

#include<bits/stdc++.h>
using namespace std;

const int N = 1000;
int n, m, idx, h[N], deg[N];
bool appear[N];
struct node {
    int to, ne;
} e[N];

void add(int u, int v) {
    e[++ idx].to = v;
    e[idx].ne = h[u];
    h[u] = idx;
    deg[v] ++;
    appear[u] = 1;
    appear[v] = 1;
}

int cpy[N];

int find() {
    int res = 0;
    for(int i = 1; i <= n; i ++) 
        if(!cpy[i]) {
            if(res) return -1;
            res = i;
        }
    return res;
}

string order;
int topo() {
    order.clear();    
    for(int i = 1; i <= n; i ++) 
        cpy[i] = deg[i];
    int st = find();
    if(!st) return 0;
    if(!~st) return -1;
    queue<int> q;
    q.push(st);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u - 1 + 'A');
        bool flag = 0;
        for(int i = h[u]; ~i; i = e[i].ne) {
            int v = e[i].to;
            if(-- cpy[v] == 0) {
                if(flag) return -1; //无法确定顺序
                flag = 1;
                q.push(v);
            }
        }
    }
    int n_of_appear = 0;
    for(int i = 1; i <= n; i ++)
        if(appear[i]) n_of_appear ++;
    if(order.size() < n_of_appear) return 0;
    else return 1;
}

int main() {
    int u, v;
    char s1, s2;
    memset(h, -1, sizeof h); 
    scanf("%d%d", &n, &m);
    bool finished = 0;
    for(int i = 1; i <= m; i ++) {
        getchar();
        scanf("%c<%c", &s1, &s2);
        if(finished) continue;
        u = s1 - 'A' + 1; v = s2 - 'A' + 1;
        if(u == v) {
            finished = 1;
            printf("Inconsistency found after %d relations.\n", i);
        }
        add(u, v);
        int res = topo();
        if(res == 1) {
            printf("Sorted sequence determined after %d relations: %s.\n", i, order.c_str());
            finished = 1;
        }
        else if(res == 0) {
            printf("Inconsistency found after %d relations.\n", i);
            finished = 1;
        }
    }
    if(!finished) 
        printf("Sorted sequence cannot be determined.\n");
}
2024/3/2 15:06
加载中...