Graphs

1.1 FIND PATH

#define SIZE 1001

int MAT[SIZE][SIZE];
int SORT[SIZE];

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
class CStack
{
public:
	CStack()
		: m_nTop(-1)
		, m_nCycleIndex(-1)
	{}

	void Push(int nValue)
	{
		m_arrStack[++m_nTop] = nValue;
	}

	int Pop() {
		int nValue = m_arrStack[m_nTop];
		--m_nTop;
		return nValue;
	}

	int Peep() const {
		return m_arrStack[m_nTop];
	}

	int IsEmpty() const {
		if(-1 == m_nTop) return true;
		return false;
	}

	void PrintPath()
	{
		cout << "Path: ";
		for(int i = m_nTop; i >= 0; i--) {
			cout << m_arrStack[i] << " ";
		}
		cout << endl;
	}

	void PrintCycle(int nNodes)
	{
		cout << "Path: ";
		for(int i = m_nCycleIndex; i <= m_nTop; i++) {
			SORT[m_arrStack[i]] = 1;
		}

		for(int i = 1; i <= nNodes; i++) {
			if (0 != SORT[i]) {
				cout << i << " ";
			}
		}
		cout << endl;
	}

	int m_nTop;
	int m_nCycleIndex;
	int m_arrStack[SIZE];
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
class CVertexInfo
{
public:
	CVertexInfo()
		: m_nParent(-1)
		, m_bVisited(false)
	{}

	void Reset()
	{
		m_nParent = -1;
		m_bVisited = false;
	}

	int m_nParent;
	bool m_bVisited;
};

class CFindPaths
{
public:
	CFindPaths(int N, int E)
		: m_nNode(N)
		, m_nEdge(E)
	{
		for(int r = 1; r <= m_nNode; r++) {
			SORT[r] = 0;
			for(int c = 1; c <= m_nNode; c++) {
				MAT[r][c] = 0;
			}
		}
	}

	void Insert()
	{
		for(int e = 0; e < m_nEdge; e++) {
			int from, to;
			cin >> from >> to;
			MAT[from][to] = 1;
		}
	}

	void Print()
	{
		for(int r = 1; r <= m_nNode; r++) {
			for(int c = 1; c <= m_nNode; c++) {
				cout << MAT[r][c] << " ";
			}
			cout << endl;
		}			
	}

	void Run(int nStart, int nEnd) 
	{
		dfs(nStart, nEnd);
	}


protected:
	bool dfs(int nStart, int nEnd)
	{
		// Start by pushing the first vertex and mark it visited
		m_objStack.Push(nStart);
		m_objVI[nStart].m_bVisited = 1;

		while(false == m_objStack.IsEmpty()) {
			int nVertex = m_objStack.Peep();
			if(nVertex == nEnd) {
				m_objStack.PrintPath();
				break;
			}

			// Flag to check if the Vertex has edges
			bool bPop = true;

			// Lookup breadth-wise and find edge
			for(int nChild = 1; nChild <= m_nNode; nChild++) {
				if (1 == MAT[nVertex][nChild]) {
					// If not visited then add to stack
					if(!m_objVI[nChild].m_bVisited) {
						bPop = false;
						m_objStack.Push(nChild);
						m_objVI[nChild].m_bVisited = 1;
						break;
					}
				}
			}

			// Pop if there is not edges from the vertex
			if(bPop) {
				m_objStack.Pop();
			}
		};

		return false;
	}

private:
	int m_nNode, m_nEdge;
	CStack m_objStack;
	CVertexInfo m_objVI[SIZE];
}; 

int main()
{
	freopen("Graph_FindPath.txt", "r", stdin);

	for(int t = 1; t <= 2; t++) {
		cout << ">>> Test Case: " << t << endl;
		int a, b;
		cin >> a >> b;
		CFindPaths obj(a, b);
		obj.Insert();
		obj.Print();
		cin >> a >> b;
		obj.Run(a, b);
	}

	return 0;
}

Input

4 5
1 2 1 3 3 1 3 4 4 4
1 4
5 6
1 2 2 3 3 1 1 4 4 5 5 1
3 5