#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的下一個鄰接頂點		   }		}