POJ4084拓扑排序--DFS的应用

描述

给出一个图的结构，输出其拓扑排序序列，要求在同等条件下，编号小的顶点在前。

输入若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有2个数，分别是该条弧所关联的两个顶点编号。
v<=100, a<=500 输出若干个空格隔开的顶点构成的序列(用小写字母)。样例输入

样例输出

v1 v3 v2 v6 v4 v5

解题思路：

这道题属于拓扑图排序问题，WA很多次。。。。最后终于过了。首先，咱们得懂什么是拓扑图，请看下面的文章

有以下两点特点：1.网上的结题报告都是WA！2.这道题要求同等条件小数在前，，，，所以这道题既不能用深搜

（一条路走到底），也不能用横向的广搜（破坏队列内部的从小到大排序），而是，，，，没错！！！用简单的

数组加上for循环就可以了，而且每次循环进入队列的只有一个！一个！！一个！！！，（防止队列中同等条件

小数排在大数前面）。本人WA了8次，终于解决了这个神问题！第一次WA：CE！没注意点的标号是从1开始的，

数组大小开的不够~第二次WA：用深搜做的，GG了第三次WA：for循环没有加break（进入队列的只有一个）~

以下是本菜鸡的菜鸡代码~

//全网唯一AC结题报告~~~菜鸡是哈尔滨工业大学李金泽先生！！！

#include<iostream>
#include<queue>
#include<list>
#include<string.h>
using namespace std;
bool visited[105];
class Graph
{
	int v;//记录顶点个数
	int *in_index;//数组，in_index[i]=j表明i节点入度为j
	list<int> *adjest;//数组，adjest[i]表明i节点邻接的点的代号
	queue<int> q;//存放入度为0的节点的代号
public:
	Graph(int v);//构造函数
	~Graph();//析构函数
	void AddDot(int a, int b);
	void CreateTuoPu();
};
Graph::Graph(int a)
{
	v = a;
	adjest = new list<int>[a + 5];//分配内存空间，为何加5你知道咩~，下标从1开始的，只开a大小的数组，绝逼编译出错，告诉你巴拉巴拉内存什么位置出错！
	in_index = new int[a + 5];//原因同上，增大数组内存
	//memset(in_index, 0, sizeof(in_index));//初始化每一个点的入度都是0
	for (int i = 1; i < a + 5; i++) { in_index[i] = 0; }
}
Graph::~Graph()
{
	delete []adjest;//释放数组内存
	delete[]in_index;//释放数组内存
}
void Graph::AddDot(int a, int b)
{
	adjest[a].push_back(b);//将b压入a的数组
	in_index[b] ++;//b的入度增加一
}
void Graph::CreateTuoPu()
{
	for (int i = 1; i <= v; i++)//将第一个入度为0的点压入队列
	{
		if (in_index[i] == 0) 
		{ 
			q.push(i); 
			visited[i] = 1;
			break;
		}//DFS
	}
	while (!q.empty())
	{
		int a = q.front();
		q.pop();
		//以上2句为去取出队列的首个节点
		cout << "v" << a << " ";
		list<int>::iterator it;
		for (it = adjest[a].begin(); it != adjest[a].end(); it++)
		{
			int b = *it;
			in_index[b] --;//b的入度减去一
		}
		for (int i = 1; i <= v; i++)
		{
			if (in_index[i] == 0 && visited[i] == 0)
			{
				q.push(i);
				visited[i] = 1;
				break;
			}	
		}
	}
}
int v, a;
int d, e;
int main()
{
	memset(visited, 0, sizeof(visited));
	cin >> v >> a;
	Graph g(v);
	for (int i = 1; i <= a; i++)
	{
		cin >> d >> e;
		g.AddDot(d, e);
	}
	g.CreateTuoPu();
	system("pause");
	return 0;
}

秒客网

POJ4084拓扑排序--DFS的应用

相关文章