데이터 구조그림무방 향도 의 관절 점 을 구하 다

"head.h"
#include<iostream>
using namespace std;

#define MAX_VEX_NUM 20

class ChildNode//                   
{
public:
	ChildNode();
	int child;
	ChildNode *next;
};

ChildNode::ChildNode()
{
	child=0;
	next=NULL;
}

class VexNode//    
{
public:
	VexNode();
	char name;
	int visitsq;//    
	int low;//low 
	ChildNode *firstchild;
};

VexNode::VexNode()
{
	visitsq=low=0;
	firstchild=NULL;
}

class VexBox//    
{
public:
	VexBox();
	int vexnum;
	VexNode vexbox[MAX_VEX_NUM];
};

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

class ArtPoint//Articulation Point//    
{
public:
	void GetArtPoint();//    
private:
	void GetVexNode();//      
	void GetEdge();//      
	void FindArticul();//    
	void DFSArticul(int);//       
	VexBox v;
	int count;
};

void ArtPoint::GetArtPoint()//    
{
	GetVexNode();//      
	GetEdge();//      
	FindArticul();//    
}

void ArtPoint::GetVexNode()//      
{
	cout<<"Please Input The Name Of The Vertex :"<<endl<<endl;
	char name;
	while(cin>>name)
	{
		v.vexbox[v.vexnum++].name=name;
	}
	cin.clear();
}

void ArtPoint::GetEdge()//      
{
	cout<<"Please Input The Two Nodes Which Made A Edge :"<<endl<<endl;
	int t[2];
	ChildNode *p,*newnode;
	while(cin>>t[0]>>t[1])
	{
		for(int i=0;i<2;i++)
		{
			newnode=new ChildNode;
			newnode->child=t[1-i];
			if((p=v.vexbox[t[i]].firstchild)==NULL)
			{
				v.vexbox[t[i]].firstchild=newnode;
			}
			else
			{
				while(p->next!=NULL)
				{
					p=p->next;
				}
				p->next=newnode;
			}
		}
	}
	cin.clear();
}

void ArtPoint::FindArticul()//    
{
	count=1;//   count      
	v.vexbox[0].visitsq=1;
	DFSArticul(0);//          
	if(count<v.vexnum)//                 
	{
		cout<<v.vexbox[0].name<<endl;//          
	}
	for(int i=1;i<v.vexnum;i++)//           
	{
		if(v.vexbox[i].visitsq==0)
		{
			DFSArticul(i);
		}
	}
}

void ArtPoint::DFSArticul(int n)//       
{
	//    low     MIN{         ,     low ,         }
	int min=v.vexbox[n].visitsq=++count;//   min
	ChildNode *p=v.vexbox[n].firstchild;
	while(p!=NULL)//               
	{
		if(v.vexbox[p->child].visitsq==0)//        
		{
			DFSArticul(p->child);//             
			if(v.vexbox[p->child].low<min)//       low    min 
				min=v.vexbox[p->child].low;//       low 
			if(v.vexbox[p->child].low>=v.vexbox[n].visitsq)//       low              
				//                              
				cout<<v.vexbox[n].name<<endl;//       
		}else if(v.vexbox[p->child].visitsq<min)//        //      min
			min=v.vexbox[p->child].visitsq;
		p=p->next;
	}//while
	v.vexbox[n].low=min;//       min       low 
}

"main.cpp"
#include"head.h"

int main()
{
	ArtPoint p;
	p.GetArtPoint();
	system("pause");
}

좋은 웹페이지 즐겨찾기