【问题描述】给定有向图的adjacent list,写出其拓扑排序结果
【输入形式】节点数目n,和有向图的 adjacent list。每个节点i的adjacent list 表示为数组[i,x,x]; 如第0个顶点和第1,5个有有向边,表示为[0 1 5]
【输出形式】拓扑排序结果
【样例输入】
10
[0 6 1 4]
[1 2]
[2 7 5]
[3 8]
[4 5]
[5 9]
[6 3 2]
[7 8]
[8 9]
[9 ]
【样例输出】[ 0 6 1 4 3 2 7 5 8 9]
我的代码:
GraphList(int numVert)
{
numVertice = numVert;
int i;
graph = new list * [numVert];
for (i = 0; i < numVert; i++)
graph[i] = new list;
char ch = '[';
for (i = 0; i < numVert; i++)
{
cin.get(ch);
cin >> graph[i]->n;
graph[i]->next = NULL;
list* p = new list();
p = graph[i];
while (ch != ']')
{
list* q = new list();
cin.get(ch);
cin >> q->n;
q->next = NULL;
p->next = q;
p = p->next;
}
}
}
int first(int v)
{
if (graph[v]->next)return graph[v]->next->n;
return -1;
}
int next(int v1, int v2)
{
if (v1 == v2)return graph[v1]->next->n;
if (graph[v2]->next)return graph[v2]->next->n;
return -1;
}
void topsort(queue<int>* Q)
{
int* indegree = new int[numVertice];
int v, w;
for (v = 0; v < numVertice; v++)
indegree[v] = 0;
for (v = 0; v < numVertice; v++)
for (w = this->first(v); w != -1; w = this->next(v, w))
indegree[w]++;
for (v = 0; v < numVertice; v++)
if (indegree[v] == 0)
Q->push(v);
cout << '[';
while (Q->size() != 0)
{
v = Q->front();
cout << " "<< v ;
Q->pop();
for (w = this->first(v); w != -1; w = this->next(v, w))
{
indegree[w]--;
if (indegree[w] == 0)
Q->push(w);
}
}
cout << ']';
}
};
int main()
{
int n; cin >> n;
GraphList* graph = new GraphList(n);
queue* q = new queue;
graph->topsort(q);
}
代码问题出在构造函数GraphList中,具体是:
cin.get(ch)得到的ch是一个换行符(要连续三次cin.get(ch) ch 才为'[' ),后面的while循环也出问题。
烦请各位指出我的问题。