ZOJ 1060 Sorting It All Out

Description

n个点，m个关系描述

三种情况：

1.只用前几个关系即可排序

2.未完成排序就发现了矛盾

3.描述太少不能排序

Link http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=60

拓扑排序（判环）

不同的是，此题要求排序是唯一的，排序不唯一视为不能排序

for(int i = 0; i < n; ++i)
        if(!in[i] && flag[i])///入度为0且被提到的字符才可入队
            q.push(i);
    while(q.size())
    {
        if(q.size() > 1)///最初入队数>1则排序不唯一
            sign = 1;

Code

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;///n个点， m个关系描述
int in[30];
int real_in[30];
int node_num;///已有点
bool flag[30];///所涉字符
bool vis_sort;///明确答案（排序完毕）
bool vis_conflict;///明确答案（明确矛盾）
bool sign;///能排序但不唯一 即 不能排序
int step_sort;
int step_conflict;
vector<int> v[30];
vector<int> ans;

void bfs(int step)
{
    sign = 0;
    ans.clear();
    for(int i = 0; i < n; ++i)
        in[i] = real_in[i];
    queue<int> q;
    for(int i = 0; i < n; ++i)
        if(!in[i] && flag[i])///入度为0且被提到的字符才可入队
            q.push(i);
    int sum = 0;///入队节点数
    while(q.size())
    {
        if(q.size() > 1)///最初入队数>1则排序不唯一
            sign = 1;
        int tem = q.front();
        ans.push_back(tem);
        sum++;
        if(sum == n)
            if(!sign)
            {
                vis_sort = 1;///找到(唯一的)答案
                step_sort = step;
            }
        q.pop();
        for(int i = 0; i < v[tem].size(); ++i)
        {
            in[ v[tem][i] ]--;///入度少的先排在前面，入度多的后放
            if(in[ v[tem][i] ] == 0)
                q.push(v[tem][i]);
        }
    }
    if(sum != node_num)
    {
        vis_conflict = 1;
        step_conflict = step;
    }
    return ;
}

int main()
{
    while(cin >> n >> m)
    {
        vis_sort = 0;///是否找到答案
        vis_conflict = 0;///是否确定矛盾
        node_num = 0;
        memset(real_in, 0, sizeof(real_in));
        memset(flag, 0, sizeof(flag));
        for(int i = 0; i < 30; ++i)
            v[i].clear();
        ans.clear();

        if(n == 0 && m == 0)
            break;

        string s;
        for(int i = 1; i <= m; ++i)
        {
            cin >> s;
            if(vis_conflict || vis_sort)///明确矛盾后只顾完成输入即可
                continue;
            int a = s[0] - 'A' ;///字符映射到 0 ~ n - 1
            if(!flag[a])
            {
                node_num++;
                flag[a] = 1;
            }
            int b = s[2] - 'A' ;
            if(!flag[b])
            {
                node_num++;
                flag[b] = 1;
            }

            v[a].push_back(b);
            real_in[b]++;

            bfs(i);
        }

        if(vis_conflict)
            printf("Inconsistency found after %d relations.\n", step_conflict);
        else if(vis_sort)
        {
            printf("Sorted sequence determined after %d relations: ", step_sort);
            int sz = ans.size();
            for(int i = 0; i < sz; ++i)
                cout << char(ans[i] + 65);
            cout << '.' << '\n';
        }
        else
            cout << "Sorted sequence cannot be determined." << '\n';
    }
    return 0;
}

多次增删，代码已不再精简，建议看以下代码

Someone’s code

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#define MM(s,q) memset(s,q,sizeof(s))
#define INF 0x3f3f3f3f
#define MAXN 100005
#define Lchild id<<1
#define Rchild (id<<1)+1
using namespace std;

int in[MAXN], In[MAXN], flag,  vis[30], finish, wrong;
char s[10];
string ans;
vector<int> vec[60];

void topsort(int n, int t) {
    for (int i = 1; i <= n; i++) in[i] = In[i];

    int  cnt = 0; // 已经出现的数目
    queue<int> Q;
    for (int i = 1; i <= n; i++)
        if (vis[i]) {
            cnt++;
            if (in[i] == 0) Q.push(i);
        }

    int num = 0, sign = 0; // num->拓扑排序中出现的元素个数
    while (!Q.empty()) {
        if (Q.size() > 1) sign = 1; // 这次拓扑排序序列不唯一
        int u = Q.front();
        num++;
        Q.pop();
        ans[num - 1] = (char)(u - 1 + 'A');
        for (int i = 0; i < vec[u].size(); i++) {
            int v = vec[u][i];
            in[v]--;
            if (in[v] == 0) Q.push(v);
        }
    }

    ans[num] = '\0';
    if (num < cnt) { // 出现环
        flag = 1, wrong = t;
        return;
    }
    if (sign == 1) return; // 不确定

    if (cnt == n)  // 序列唯一
        flag = 1, finish = t;
}
int main() {
    int n, m, a, b;
    while (cin >> n >> m && n && m) {

        MM(In, 0);
        MM(vis, 0);
        flag = finish = wrong = 0;
        for (int i = 1; i <= n; i++)vec[i].clear();

        for (int i = 1; i <= m; i++) {
            scanf("%s", s);
            a = s[0] - 'A' + 1, b = s[2] - 'A' + 1;
            vis[a] = vis[b] = 1;
            vec[a].push_back(b);
            In[b]++;
            if (flag == 0)  // 还没有结果
                topsort(n, i);
        }

        if (finish) printf("Sorted sequence determined after %d relations: %s.\n", finish, ans.c_str());
        else if (wrong) printf("Inconsistency found after %d relations.\n", wrong);
        else printf("Sorted sequence cannot be determined.\n");
    }

}