#include "stack.h"
#include "P267E.cpp"


struct BiEdge
{
		BiEdge(){a=b=0;};
		BiEdge(int p1, int p2):a(p1),b(p2){};
		void SetVertex(int p1, int p2){a=p1;b=p2;};
		int operator==(BiEdge e)
		{
		  return ((a==e.a)&&(b==e.b)) || ((a==e.b)&&(b==e.a));
		};
		int a,b;
};
ostream& operator <<(ostream& strm, BiEdge& e)
{
  strm<<"("<<e.a<<","<<e.b<<")";
  return strm;
};

static int * dfn,*low;

//static int dfn[MaxNumVertices];
//static int low[MaxNumVertices];


static int num;


static  Stack< BiEdge >   S(MaxNumEdges);
static int min2(const int a, const int b)
{
	return a>b?b:a;
};



template <class NameType, class DistType> 
void Graph<NameType,DistType>::DfnLow ( const int x ) {				//從頂點x開始深度優先搜索
		   num = 1;							// num是訪問計數器, 是一個整型數據
		   dfn = new int[NumVertices];					// dfn是深度優先數, 是一個整型數組
		   low = new int[NumVertices];					// low是最小祖先訪問順序號, 是一個整型數組
		   for ( int i=0; i<NumVertices; i++ ) { dfn[i] = low[i] = 0; }
		   DfnLow ( x, -1 );
		   delete [ ] dfn;  delete [ ] low;
		}

template <class NameType, class DistType> 
void Graph<NameType,DistType>::DfnLow ( const int u, const int v ) {
		//從頂點u開始深度優先搜索計算dfn和low。在產生的生成樹中v是u的雙親。
		   dfn[u] = low[u] = num++;					//給予訪問計數器num及dfn[u], low[u]初值
		   int w = GetFirstNeighbor (u);
		   while ( w != -1 ) {						//對頂點u的所有鄰接頂點w循環
			 if ( dfn[w] == 0 ) {					//未訪問過, w是u的孩子
			   DfnLow ( w, u );					//遞歸深度優先搜索
			   low[u] = min2 ( low[u], low[w] );			//low[ ]的值是逆向計算, 先求出子女的再求自身
			 }
			 else if ( w != v )						//除去(u, v)邊以外, (u, w)都是回邊
				  low[u] = min2 ( low[u], dfn[w] );		//取兩者中的小者
			 w = GetNextNeighbor (v, w);				//找頂點v的下一個鄰接頂點
		   }
		}
template <class NameType, class DistType> 
void Graph<NameType,DistType>::Biconnected ( ) {
		   num = 1;								//訪問計數器num是一個整型數據
		   dfn = new int[NumVertices];						// dfn是深度優先數, 是一個整型數組
		   low = new int[NumVertices];						// low是最小祖先順序號, 是整型數組
		   for ( int i=0; i<NumVertices; i++ ) { dfn[i] = low[i] = 0; }
//		   DfnLow ( 0, -1 );							//從頂點0開始
		   Biconnected(0,-1);
		   delete [ ] dfn;  delete [ ] low;
		}

template <class NameType, class DistType> 
void Graph<NameType,DistType>::Biconnected ( const int u, const int v ) {
		//計算dfn與low, 并根據其重連通分量輸出G的邊。在產生的生成樹中, v是u的父結點, S是一個初始為空的
		//棧, 它被聲明為圖的數據成員。
		   int w;
		   BiEdge e;
		   dfn[u] = low[u] = num++;		   
		   w = GetFirstNeighbor (u);						//找頂點u的第一個鄰接頂點;
		   while ( w != - 1 ) {							//w是v的鄰接頂點
			 if ( v != w && dfn[w] < dfn[u] ) S.Push ( BiEdge(u,w) );
			 if ( dfn[w] == 0 ) {						//未訪問過, w是的孩子
			   Biconnected (w, u);						//遞歸深度優先訪問
			   low[u] = min2 ( low[u], low[w] );
			   if ( low[w] >= dfn[u] ) {					//無回邊, 原來的重連通分量結束
				 cout << "New Biconnected Component: " << endl;
				 do {
				   e = S.Pop ( );					//輸出該重連通分量的各邊 
	 			   cout << GetValue(e.a) <<"-"<<GetValue(e.b)<< endl;
				 } while ( !(e==BiEdge(u,w)));
			   }
			 }
			 else if ( w != v ) low[u] = min2 ( low[u], low[w] );		//有回邊, 計算
			 w = GetNextNeighbor (u, w);					//找頂點v的下一個鄰接頂點
		   }
		}