c++ - 图可排序性 C++

Question

所以我有一个家庭作业问题:

Let G be a directed graph on n vertices.

Call G sortable if the vertices can be distinctly numbered from 1 to n (no two vertices have the same number) such that each vertex with incoming edges has at least one predecessor with a lower number. For example, Let NUM(v) be the number assigned to vertex v and consider a vertex x with incoming edges from three other vertices r, y, and z. Then NUM(x) must be bigger than at least one of NUM(r), NUM(y), and NUM(z).

此外，算法必须是线性的； O(|V|+|E|)。

---

遍历图很容易，但我不知道如何检查顶点的父节点以查看父节点的 any 数量是否低于子节点的数量。

我应该如何保持对我所在顶点的父级的引用？

---

以下邻接表是输入文件(实际测试用例的样本大约有 8k 个顶点)。

1->2
2->3
3->1

Is not Sortable.

1->2
2->3
3->4
4->2

Is Sortable.

---

这个问题可以用 C++/C 来解决，我选择了 C++ 来使用 STL。

我使用邻接列表存储图形，输入文件是边列表。

Answer 1

这样可以吗？

1. 创建邻接矩阵。如果row 指向col，则放一个1 那里。
2. 向下扫描每个 col 到第一个 1。如果 col <= row 则失败。
3. 否则，通过。

以下是您的两个示例的表格:

  1 2 3
1 0 1 0
2 0 0 1
3 1 0 0

  1 2 3 4
1 0 1 0 0
2 0 0 1 0
3 0 0 0 1
4 0 1 0 0

如果您担心空间，因为它必须处理 8k 个顶点，那么如果您知道输入是稀疏的，则可以使用稀疏表示。但实际上，我认为 64M 整数不应该引起关注。

GCC 4.7.3: g++ -Wall -Wextra -std=c++0x sortable-graph.cpp

#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

std::string trim(const std::string& str) {
  std::string s;
  std::stringstream ss(str);
  ss >> s;
  return s;
}

using graph = std::vector<std::vector<int>>;

graph read(std::istream& is) {
  graph G;
  std::vector<std::pair<int, int>> edges;
  std::map<std::string, int> labels;
  int max = -1;

  // Assume input is a list of edge definitions, one per line. Each line is:
  // "label -> label" where white space is optional, "->" is a literal, and
  // "label" does not contain "->" or white space.

  // This can be vastly simplified if we can assume sensible int labels.

  std::string l;
  while (std::getline(is, l)) {
    // Parse the labels.
    const auto n = l.find("->");
    const auto lhs = trim(l.substr(0, n));
    const auto rhs = trim(l.substr(n + 2));

    // Convert the labels to ints.
    auto i = labels.find(lhs);
    if (i == labels.end()) { labels[lhs] = ++max; }
    auto j = labels.find(rhs);
    if (j == labels.end()) { labels[rhs] = ++max; }

    // Remember the edge.
    edges.push_back({labels[lhs], labels[rhs]});
  }

  // Resize the adjacency matrix.
  G.resize(max+1);
  for (auto& v : G) { v.resize(max+1); }

  // Mark the  edges.
  for (const auto& e : edges) { G[e.first][e.second] = 1; }

  return G;
}

bool isSortable(const graph& G) {
  const int s = G.size();
  for (int col = 0; col < s; ++col) {
    for (int row = 0; row < s; ++row) {
      if (G[row][col] == 1) {
        if (col <= row) { return false; }
        break;
      }
    }
  }
  return true;
}

void print(std::ostream& os, const graph& G) {
  const int s = G.size();
  for (int row = 0; row < s; ++row) {
    for (int col = 0; col < s; ++col) {
      os << G[row][col] << " ";
    }
    os << "\n";
  }
}

int main() {
  const auto G = read(std::cin);
  print(std::cout, G);
  const auto b = isSortable(G);

  std::cout << (b ? "Is Sortable.\n" : "Is not Sortable.\n");
}

现在我看了一下，我猜这是 O(V^2)。