Как определить, имеет ли граф неуникальную топологическую сортировку

Я создал программу, которая организует график по топологической сортировке с учетом диаграммы. Я определил 3 результата:

  • Хорошо
  • существующие циклы
  • недостающая информация

Вывод первых двух точек правильный, но для третьего это не так. Например, для графа с 4 вершинами и ребрами: 1-> 2; 3-> 1; 3-> 4; 4-> 2, результат, который я получил: 3 1 4 2 … неправильно! То, что известно, недостаточно, чтобы заключить это.
Любые советы или помощь приветствуется, спасибо заранее.

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

class Graph{
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int u, int v);
void topologicalSort();
};

Graph::Graph(int V){
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int u, int v){
adj[u].push_back(v);
}

void Graph::topologicalSort(){
vector<int> in_degree(V, 0);
for (int u=0; u<V; u++){
list<int>::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
in_degree[*itr]++;}
queue<int> q;
for (int i = 0; i < V; i++)
if (in_degree[i] == 0)
q.push(i);
int cnt = 0;
vector <int> top_order;
while (!q.empty()){
int u = q.front();
q.pop();
top_order.push_back(u);
list<int>::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
if (--in_degree[*itr] == 0)
q.push(*itr);
cnt++;}
if (cnt != V){
cout << "Existing cycle\n";
return;}
for (int i=1; i<(int)top_order.size(); i++)
cout << top_order[i] << " ";
cout << endl;
}

int main(){
setbuf(stdout, NULL);
int N, L, u, v;
scanf("%d %d", &N, &L);
Graph g(N+1);
for (int i=1; i<=L; i++){
scanf("%d %d", &u, &v);
g.addEdge(u, v);
}
g.topologicalSort();
return 0;
}

0

Решение

Чтобы проверить, что конкретный граф имеет уникальную топологическую сортировку, достаточно проверить гамильтонову траекторию в DAG. Цитирование википедии:

Если топологическая сортировка обладает тем свойством, что все пары последовательных вершин в отсортированном порядке связаны ребрами, то эти ребра образуют направленный гамильтонов путь в DAG. Если существует гамильтонов путь, топологический порядок сортировки уникален; никакой другой порядок не учитывает края пути. И наоборот, если топологическая сортировка не образует гамильтонова траектория, группа обеспечения доступности баз данных будет иметь два или более допустимых топологических порядка, поскольку в этом случае всегда можно сформировать второй действительный порядок путем замены двух последовательных вершин, которые не соединены ребром. друг другу. Следовательно, можно проверить в линейном времени, существует ли уникальный порядок.

Так что вам просто нужно получить DAG для первой найденной сортировки и убедиться, что она образует путь, который посещает все вершины.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]