main.cpp

一个我的数据结构解题集合

#include <iostream>
#include <string>
#include "IoUtils.h"
#include "Graph.h"
using namespace std;


template <typename T>
class StrongComponents {
private:
	/* id:		保存该端点所在强连同分量的编号
	 * order:	保存结点的退出次序，order[i]表示第i个退出的结点
	 */
	Vector<int> id, order;

	int cnt, idcnt;

	void markVertex(int i, const Graph<T>& graph) {
		id[i] = idcnt;
		for ( SList<int>::Itor itor = graph.vertices()[i].adjvert.begin();
			  itor != graph.vertices()[i].adjvert.end();
			  itor = itor->next ) {
			if ( id[itor->data] == -1 )
				markVertex(itor->data, graph);
		}
		order[cnt++] = i;
	}

public:
	/* 求有向图g的强连同分量
	 */
	StrongComponents(const Graph<T>& g) {
		int i;
		order.enlarge(g.vertices().size());
		id.enlarge(g.vertices().size());
		for (i = 0; i < id.size(); ++i)		// 清空id
			id[i] = -1;

		cnt = idcnt = 0;
		for (i = 0; i < id.size(); ++i) {
			if (id[i] == -1) markVertex(i, g);
		}

		Vector<int> orderR;
		orderR = order;		// 保存本次遍历得到的退出次序

		cnt = idcnt = 0;
		for (i = 0; i < id.size(); ++i)		// 清空id
			id[i] = -1;

		Graph<T> r = g.reverse();
		for (i = id.size() - 1; i >=0; --i) {
			if (id[orderR[i]] == -1) {
				markVertex(orderR[i], r);
				++idcnt;
			}
		}
	} // StrongComponents(const Graph<T>&)

	/* 查询强连同分量的个数 */
	int count() const { return idcnt; }

	/* 查询求出的各个强连同分量 */
	const Vector<int>& strongComponentsId() const {
		return id;
	} // strongComponentsId() const

}; // StrongComponents

int main() {
	Graph<int> g;

	cout << "本程序用来求图的强连同分量，以数字代表结点，"
		 << "当输入中有一个负数时输入结束"
		 << endl;
	
	int v1, v2;
	while (true) {
		cout << "输入起始结点: ";
		v1 = getInteger();
		cout << "输入终止结点: ";
		v2 = getInteger();
		if (v1 < 0 || v2 < 0)
			break;
		g.insert(v1, v2);
	}
	
	Vector<int> id = StrongComponents<int>(g).strongComponentsId();
	cout << "Vertex\tSC Group\n";
	for (int i = 0; i < id.size(); ++i) {
		cout << g.vertices()[i].data << ":\t" << id[i] << "\n";
	}
	cout << endl;

	pause();
	return 0;

} // main()