所以我有一个家庭作业问题：
设
G为顶点上的有向图n。
G如果顶点可以从1到明确编号（没有两个顶点具有相同的编号），则调用sortablen，使得每个具有传入边的顶点至少有一个编号较小的前任。例如，让NUM(v)是分配给顶点的数字，v并考虑一个顶点，该顶点x具有来自其他三个顶点r、y和的传入边z。然后NUM(x)必须大于NUM(r)、NUM(y)和中的至少一个NUM(z)。
此外，算法必须是线性的；O(|V|+|E|).
遍历图表很容易，但我不知道如何检查顶点的父母以查看是否有任何父母的数量低于孩子的数量。
我应该如何保持对我所在顶点的父母的引用？
以下邻接列表是输入文件（仅对实际测试用例具有大约 8k 个顶点的样本进行采样）。
1->2
2->3
3->1
Is not Sortable.
1->2
2->3
3->4
4->2
Is Sortable.
这个问题可以在 C++/C 中完成，我选择了 C++ 来使用 STL。
我使用邻接列表存储图形，输入文件是边列表。
这会做吗？
row指向col，则将 a 放在1
那里。col到第一个1。如果col<=row那么fail.pass。以下是您的两个示例的表格：
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)。
拿两个！这个是 O(|V|+|E|)。
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 edges = std::vector<std::pair<int, int>>;
void read(std::istream& is, edges& E, int& max) {
std::map<std::string, int> labels;
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.
E.push_back({labels[lhs], labels[rhs]});
}
}
bool isSortable(const edges& E, int max) {
std::vector<int> num(max+1, max+1);
for (const auto& e : E) {
num[e.second] = std::min(e.first, num[e.second]);
}
for (int i = 0; i < num.size(); ++i) {
if (num[i] != max + 1 && i <= num[i]) { return false; }
}
return true;
}
int main() {
edges E;
int max;
read(std::cin, E, max);
const auto b = isSortable(E, max);
std::cout << (b ? "Is Sortable.\n" : "Is not Sortable.\n");
}