#include
#include
using?namespace?std;
//最大權(quán)值
#define?MAXWEIGHT?100
//邊節(jié)點
typedef?struct?edgenode_tag
{
	int?adjvex;??//鄰接點
	int?weight;??//邊的權(quán)值
	struct?edgenode_tag?*next;
}EdgeNode;
//頂點節(jié)點
typedef?struct?vertex_tag
{
	int?vertex;???//頂點
	EdgeNode?*next;
}Vertex;
class?Graph
{
private:
	//是否帶權(quán)
	bool?isWeighted;
	//是否有向
	bool?isDirected;
	//頂點數(shù)
	int?numV;
	//邊數(shù)
	int?numE;
	//鄰接表
	Vertex?*adjList;
public:
	/*
	構(gòu)造方法
	numV是頂點數(shù)，isWeighted是否帶權(quán)值，isDirected是否有方向
	*/
	Graph（int?numV?bool?isWeighted?=?false?bool?isDirected?=?false）;
	//建圖
	void?createGraph（）;
	//析構(gòu)方法
	~Graph（）;
	//獲取頂點數(shù)
	int?getVerNums（）
	{return?numV;}
	//獲取邊數(shù)
	int?getEdgeNums（）
	{return?numE;}
	//插入邊
	void?insertEdge（int?tail?int?head?int?weight?=?1）;
	void?insertedge（int?tail?int?head?int?weight）;
	//設(shè)置指定邊的權(quán)值
	void?setEdgeWeight（int?tail?int?head?int?weight）;
	//打印鄰接表
	void?printAdjacentList（）;
	//檢查輸入
	bool?check（int?tail?int?head?int?weight?=?1）;
};
/*
構(gòu)造方法
numV是頂點數(shù)，isWeighted是否帶權(quán)值，isDirected是否有方向
*/
Graph::Graph（int?numV?bool?isWeighted?bool?isDirected）
{
	while?（numV?<=?0）
	{
		cout?<		cin?>>?numV;
	}
	this->numV?=?numV;
	this->isWeighted?=?isWeighted;
	this->isDirected?=?isDirected;
	//邊數(shù)初始化為0
	numE?=?0;
	adjList?=?new?Vertex[numV];??//指針數(shù)組
	for?（int?i?=?0;?i?	{
		adjList[i].vertex?=?i;
		adjList[i].next?=?NULL;
	}
}
//建圖
void?Graph::createGraph（）
{
	//用一個新的變量表示邊數(shù)，numE的修改則留到insertedge（）中
	int?numEdge?=?0;
	cout?<	while?（cin?>>?numEdge?&&?numEdge?		cout?<
	int?i?j?w;
	if?（!isWeighted）??//無權(quán)圖
	{
		cout?<		for?（int?k?=?0;?k?		{
			cin?>>?i?>>?j;
			while?（!check（i?j））
			{
				cout?<				cin?>>?i?>>?j;
			}
			insertEdge（i?j）;
		}
	}
	else??//有權(quán)圖
	{
		cout?<		for?（int?k?=?0;?k?		{
			cin?>>?i?>>?j?>>?w;
			while?（!check（i?j?w））
			{
				cout?<				cin?>>?i?>>?j?>>?w;
			}
			insertEdge（i?j?w）;
		}
	}
}
//析構(gòu)方法
Graph::~Graph（）
{
	int?i;
	EdgeNode?*p?*q;
	for?（i?=?0;?i?	{
		if?（adjList[i].next）
		{
			p?=?adjList[i].next;
			while?（p）
			{
				q?=?p->next;
				delete?p;
				p?=?q;
			}
		}
	}
	delete[]adjList;
}
//設(shè)置指定邊的權(quán)值
void?Graph::setEdgeWeight（int?tail?int?head?int?weight）
{
	if?（!isWeighted）??//無權(quán)圖
	{
		while?（!check（tail?head））
		{
			cout?<			cin?>>?tail?>>?head;
		}
		insertEdge（tail?head）;
	}
	e