head.h

#include<iostream>
using namespace std;
#define MAX_VEX_NUM 20

class ArcNode //记录一条弧 
{
public:
	ArcNode();
	int headvex, tailvex;
	ArcNode *hlink, *tlink;
};

ArcNode::ArcNode()
{
	headvex = tailvex = 0;
	hlink = tlink = NULL;
}

class VexNode //记录一个顶点连接的所有弧
{
public:
	VexNode();
	bool visited;
	char vexname;
	ArcNode *firstin, *firstout;
};

VexNode::VexNode()
{
	visited = false;
	firstin = firstout = NULL;
}

class VexBox //顶点集合
{
public:
	VexBox();
	VexNode vexlist[MAX_VEX_NUM];
	int vexnum;
};

VexBox::VexBox()
{
	vexnum = 0;
}

class Graph //图类
{
public:
	void ShowGraph(); //接口函数
private:
	void GetVexList(); //得到顶点列表
	void CreatGraph(); //建图
	void Print(); //打印图信息
	void StrongComp(); //求强连通分量
	void DFSHead(int); //正向DFS
	void DFSTail(int); //反向DFS
	VexBox vbox;
	int count, finished[MAX_VEX_NUM], ans[MAX_VEX_NUM], nans;
};

void Graph::ShowGraph() //接口函数
{
	GetVexList(); //得到顶点列表
	CreatGraph(); //建图
	Print(); //打印图信息
	StrongComp(); //求强连通分量
}

void Graph::GetVexList() //得到顶点列表
{
	cout << "Please Input Vertexes :" << endl << endl;
	char name;
	while (cin >> name)
	{
		vbox.vexlist[vbox.vexnum++].vexname = name;
	}
	cin.clear();
}

void Graph::CreatGraph() //建图
{
	cout << "Please Input Arces :" << endl << endl;
	int head, tail;
	ArcNode *newnode, *p;
	while (cin >> tail >> head)
	{
		newnode = new ArcNode;
		newnode->headvex = head;
		newnode->tailvex = tail;
		p = vbox.vexlist[tail].firstout;
		if (p == NULL)
		{
			vbox.vexlist[tail].firstout = newnode;
		}
		else
		{
			while (p->tlink != NULL)
			{
				p = p->tlink;
			}
			p->tlink = newnode;
		}
		p = vbox.vexlist[head].firstin;
		if (p == NULL)
		{
			vbox.vexlist[head].firstin = newnode;
		}
		else
		{
			while (p->hlink != NULL)
			{
				p = p->hlink;
			}
			p->hlink = newnode;
		}
	}
	cin.clear();
}

void Graph::Print() //打印图信息
{
	ArcNode *p;
	for (int i = 0; i < vbox.vexnum; i++)
	{
		cout << vbox.vexlist[i].vexname << endl;
		p = vbox.vexlist[i].firstout;
		while (p != NULL)
		{
			cout << "\t" << vbox.vexlist[p->tailvex].vexname << "->"
					<< vbox.vexlist[p->headvex].vexname << endl;
			p = p->tlink;
		}
	}
}

void Graph::StrongComp() //求强连通分量
{
	count = 0;
	for (int i = 0; i < vbox.vexnum; i++)
	{
		if (vbox.vexlist[i].visited == false)
			DFSHead(i);
	}
	for (int i = 0; i < vbox.vexnum; i++)
		vbox.vexlist[i].visited = false;
	for (int i = count - 1; i >= 0; i--)
	{
		if (vbox.vexlist[i].visited == false)
		{
			nans = 0;
			DFSTail(i);
			if (nans > 0)
			{
				cout << vbox.vexlist[ans[0]].vexname;
				for (int i = 1; i < nans; i++)
					cout << "<->" << vbox.vexlist[ans[i]].vexname;
				cout << endl;
			}
		}
	}
}

void Graph::DFSHead(int k) //正向DFS
{
	vbox.vexlist[k].visited = true;
	ArcNode *p = vbox.vexlist[k].firstout;
	while (p != NULL)
	{
		if (vbox.vexlist[p->headvex].visited == false)
			DFSHead(p->headvex);
		p = p->tlink;
	}
	finished[count++] = k;
}

void Graph::DFSTail(int k) //反向DFS
{
	ans[nans++] = k;
	vbox.vexlist[k].visited = true;
	ArcNode *p = vbox.vexlist[k].firstin;
	while (p != NULL)
	{
		if (vbox.vexlist[p->tailvex].visited == false)
		{
			DFSTail(p->tailvex);
		}
		p = p->tlink;
	}
}

main.cpp

#include"head.h"
 
int main()
{
	Graph g;
	g.ShowGraph();
	system("pause");
}