#include
#define?MAXNODE?64
#define?NULL?0
using?namespace?std;
/*鄰接表存儲結(jié)構(gòu)*/
typedef?struct?arc
???{int?adjvex;???????????//鄰接點在頂點中的下標(biāo)
????struct?arc?*next;
}ArcNode;

typedef?struct?VexNode
{????????????????????????????
int?leftright;
?ArcNode?*firstarc;//指向第一鄰接點的指針
}VerNode;

typedef?VerNode?AdjList[MAXNODE];
/*創(chuàng)建圖*/
int?visited[MAXNODE];
??????????????????????????????????????????????????????
int?vsum;
void?creatgraph（AdjList?GL）
{int?ijk;char?y;
?ArcNode?*p;
?cout<<“請輸入村子數(shù):“;
?cin>>vsum;
???for（i=1;i<=vsum;i++）
???{????????????????????????????????????????????????
??????GL[i].firstarc=NULL;
??????}
?cout<<“請輸入村之間的所有路????一條路的兩個端點之間用，分隔\n需滿足任意兩村之間有且僅有一條路:“<?for（k=0;k?????{
??????cin>>i>>y>>j;
??????if（i&&j）
	??{
	???p=new?ArcNode;?
	???p->adjvex=j;p->next=GL[i].firstarc;GL[i].firstarc=p;
	???p=new?ArcNode;
	???p->adjvex=i;p->next=GL[j].firstarc;?GL[j].firstarc=p;
	??}
??????}
?}

/*深度優(yōu)先遍歷*/
int?i=0;
void?dfs（AdjList?Gint?v）
?{ArcNode?*q;?
if（!visited[v]）??{i++;?G[v].left=i;cout<????visited[v]=1;
????q=G[v].firstarc;
????while（q!=NULL）
?????{if（!visited[q->adjvex]）?dfs（Gq->adjvex）;
		q=q->next;
		if（q==NULL）{i++;?G[v].right=i;cout<??}
}
void?DfsAdjlist（AdjList?GLint?v）
{int?i;
?for（i=1;i<=vsum;i++）?visited[i]=0;
?if（!visited[v]）?dfs（GLv）;
?}
/*判斷c是否為a和b的最近祖先*/
void??Near（AdjList?Gint?aint?bint?c）
{int?lr;ArcNode?*q;?int?i=0;int?m=0;
int?H[32];
??q=G[c].firstarc;???????????????????????????
??if（G[a].left>G[b].left）{l=G[b].left;r=G[a].right;}
	else{l=G[a].left;r=G[b].right;}
	while?（q!=NULL）{
	if（G[c].leftadjvex].left）{//必需不是c的祖先
			m++;H[m]=G[q->adjvex].left;????//cout<		m++;H[m]=G[q->adjvex].right;???????//cout<	}
		q=q->next;
}
?	//cout<	int?low=1;int?high=m;//二分查找
	int?mid;
	while（low+1		mid=（low+high）/2;
		if（l>=H[mid]）??low=mid;
		else?high=mid-1;
	}
	switch（low%2）
	{case?0:cout<<“皇天不負(fù)有心人“<	case?1:if（r<=H[low+1]）?cout<<“白等“<		else?cout<<“皇天不負(fù)有心人“<default:cout<<“錯誤“<	???}
}

/*判斷c是否在b到c上?函數(shù)*/
void?Decide（AdjList?Gint?a?int?bint?c）{
????int?k=0;
	if（G[c].leftG[b].right）?k++;
	if（G[c].leftG[a].right）?k++;
????switch（k）{
	case?0:cout<<“白等“<	case?1:cout<<“皇天不負(fù)有心人“<	case?2:Near（Gabc）;break;??????????????????????//c為a和b祖先
	default:cout<<“Error“<	}
}
void??main（）
?{AdjList?GL;int?m=0;
??int?a[20]b[20]c[20];int?z;char?t;
??cout<<“????????????????**************神秘國度的愛情故事***************???????“<??creatgraph（GL）;
??DfsAdjlist（GL1）;
??cout<??cout<<“請輸入測試組數(shù):“;
??cin>>z;
??while（z>0）{
	z--;m++;
????cout<<“請分別輸入第“<????cin>>a[m]>>b[m]>>c[

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????548926??2011-01-04?13:01??神秘國度的愛情故事\Debug\love.exe

?????文件?????788700??2011-01-04?13:01??神秘國度的愛情故事\Debug\love.ilk

?????文件?????259005??2011-01-04?13:11??神秘國度的愛情故事\Debug\love.obj

????I.A....???2001184??2011-01-02?10:09??神秘國度的愛情故事\Debug\love.pch

?????文件????1115136??2011-01-04?13:00??神秘國度的愛情故事\Debug\love.pdb

?????文件?????123904??2011-01-04?13:11??神秘國度的愛情故事\Debug\vc60.idb

?????文件?????110592??2011-01-04?13:00??神秘國度的愛情故事\Debug\vc60.pdb

?????文件???????3378??2011-01-04?13:00??神秘國度的愛情故事\love.cpp

?????文件???????3717??2010-12-30?15:02??神秘國度的愛情故事\love.dsp

?????文件????????533??2010-12-30?16:51??神秘國度的愛情故事\love.dsw

?????文件??????50176??2011-01-05?15:57??神秘國度的愛情故事\love.ncb

?????文件??????48640??2011-01-05?15:57??神秘國度的愛情故事\love.opt

?????文件????????688??2011-01-04?13:11??神秘國度的愛情故事\love.plg

?????文件?????????56??2011-01-04?15:03??神秘國度的愛情故事\readme.txt

?????目錄??????????0??2011-01-04?13:00??神秘國度的愛情故事\Debug

?????目錄??????????0??2011-01-05?15:57??神秘國度的愛情故事

-----------?---------??----------?-----??----

??????????????5054635????????????????????16