데이터 구조그림무방 향도 의 관절 점 을 구하 다
#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");
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.