poj1094&&zoj1060 Sorting It All Out ——拓扑排序入门题

May 1, 2013
POJ Graph

题目链接：http://poj.org/problem?id=1094 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=60 题目大意：　　输入两个整数，n, m 分别表示以下的字母在字母表前 n 个字母范围内，有 m 行，每行描述一个大小关系，只有小于号。如果从开始到某一个关系式可以确定最终的序列，就输出确定的序列。如果得到矛盾，就输出到此经历的几个关系式。如果最终都没有确定，就输出序列不能确定的信息。题目思路：　　边读入，边建图，每读入一条表达式，就拓扑排序判断是不是可以确定最后的序列了。如果可以得到最后包含全部n个字母的序列，后面的表达式只需要输入，但是不需要处理了。如果过程中到达一个表达式的时候，找到了一个环，就说明肯定不能确定最后的序列了。也不需要处理后面的表达式了。如果一直都没有确定，就一直处理。　　这题大体上的思路是这样，但是还是有一些细节没有处理好。最严重的就是：如何在中间的过程中去判断环。不能单纯地比较弹栈的顶点个数和 n 的大小，因为可能读入的顶点个数还没有到达ｎ的时候，就已经出现环了，这样，以后的输入就不用处理了。如何处理呢？我的方法就是，当前剩下的点当中，是不是还存在度数大于０的点，用ｂｕｇ标记，因为这个ｂｕｇ调试了好久。。如果存在的话，就说明返回－１，表示存在环。为什么会出现这个ｂｕｇ呢？因为这个涉及到到第几条表达式出现矛盾的问题。　　主要还是思维不严谨，虽然后来测试数据过了，但还是不知道哪里错了，后来自己出了几组数据才发现那个ｂｕｇ。这题做了好久，有的人一下就过了，可是我却卡了两天……教训就是：遇到ｂｕｇ了不能慌，分析一下是不是自己当初的想法错了，还是哪个细节没有处理好。即使有一个细节处理不好，程序最后都会崩溃。还有就是，可能自己的处理方法不好，导致最后的ｂｕｇ超多，代码也超级繁琐……一开始就应该想清楚，有没有更好的处理办法，尤其是一些细节问题。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
bool edge[27][27];
int n, m, rela;
string s, out;
map<int,bool> mymap;
int Count[27], mystack[27], Count1[27];
int topsort(int ki)
{
  out.clear();
  int i, j, k, top = 0, cnt = 0; int bug = 0;
  bool flag = true;
  for (i = 0; i < 27; ++i) {
    mystack[i] = 0;
    Count1[i] = Count[i];
  }
  for (i = 0; i < n; ++i) {
    if (mymap[i] && Count1[i]==0) {
      Count1[i]--; mystack[++top] = i; cnt++;
      out += (i+'A');
    }
  }
  if (top > 1) flag = false;
  while (top>0) {
    j = mystack[top];
    top--;
    for (i = 0; i < n; ++i) {
      if (mymap[i] && edge[j][i]==true) {
        Count1[i]--;
      }
    }
    for (i = 0; i < n; ++i) {
      if (mymap[i] && Count1[i]==0) {
        Count1[i]--; mystack[++top] = i; cnt++;
        out += (i+'A');
      }
    }
    if (top > 1) flag = false;
  }
  for (i = 0; i < n; ++i) {
    if (Count1[i] > 0) {
      bug++; break;
    }
  }
  if (top == 0 && bug > 0) return -1;
  if (flag == false) return 0;
  return cnt;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1094.in", "r", stdin);
  freopen("out", "w", stdout);
#endif
  int i, j, k;
  while (~scanf("%d%d", &n, &m) && (m||n)) {
    out.clear();
    mymap.clear(); memset(edge, false, sizeof(edge));
    int mrk = 0, kind = 0, pai = 0, cnt = 0; rela = 0;
    for (i = 0; i < 27; ++i) Count[i] = 0;
    for (i = 0; i < m; ++i) {
      cin >> s;
      if (mrk == 1 || mrk == -1) continue;
      int u, v;
      rela++;
      u = s[0] - 'A'; v = s[2] - 'A';
      if (!mymap[u]) mymap[u]=true, kind++;
      if (!mymap[v]) mymap[v]=true, kind++;
      if (edge[u][v]==false) {
        edge[u][v] = true;
        Count[v]++;
      }
      pai = topsort(kind);
      if (pai == n ) mrk = 1;
      if (pai == -1) mrk = -1;
    }
    if (pai != 0 && pai < kind) mrk = -1;
    if (mrk == 1)
      printf("Sorted sequence determined after %d relations: ", rela), cout << out <<'.'<<endl;
    else if (mrk == -1)
      printf("Inconsistency found after %d relations.\n", rela);
    else if (mrk == 0)
      printf("Sorted sequence cannot be determined.\n");
  }

  return 0;
}

　　这题过的好辛苦。但是过了之后，才发现，自己原来陷入了思维的误区，一些细节自己根本没有考虑到。思维定式，总是想着自己的处理方法是对的。然后就花很长时间也找不出来错……

Read more