PAT 1139. First Contact (30) 圖的存儲+相連判斷

#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<string>
using namespace std;
//
/*************************
題意：
給出一個圖的所有邊，用"a b"來表示ab相連。
若節點帶‘-’則為女孩，不帶‘-’則為男孩。

接着給出一個查詢A到D的路徑
該路徑的要求必須如下：
	A先經過B,且A和B必須同性别
	B再給C，B和C性别不需要相同。
	最後C再給D，且C和D必須同性别

求出所有符合這個條件的B和C
*************************/

/************************
求解要點：
先考慮題目所給的資料範圍
	點的數量為0~300
	查詢的數量為0~100
同時，A到D肯定隻經過2個點，即A和D中間的點肯定是2個，且有性别要求。
那麼完全不需要什麼搜尋或者Dijkstra。
因為路徑的過程是固定的，A->B->C->D，那麼隻需要B和C是相鄰的,就一定可行！
是以:
	我們先周遊A的所有相鄰點B，排除性别與A不相同的。
	周遊A的每個相鄰且性别相同的點時：
		再去周遊D的每個相鄰且性别相同的點C
		然後判斷B和C是否相鄰，若相鄰則符合要求。
注意點：
①存儲并周遊相鄰點時用鄰接表
判斷是否相鄰用鄰接矩陣。
但由于每個點的ID範圍為0~9999，開不了那麼大的數組
而點的數量最多隻有300個
故應該設定序号數組，給每個ID做一個轉換，能夠轉換到0~300間的序号。
②A的相鄰點不能是D，D的相鄰點不能是A，因為他們必須要經過2個人傳遞。
③查詢時，A和D也是帶正負的，也要處理
④會有‘-0000’存在的情況，是以應該先輸入字元串，再轉成數字ID。
⑤輸出為4位digit，故輸出時要補0

************************/

/***********************
筆記：
1.先去思考題目條件、範圍的特點，再去想用哪個方法。
2.當點的ID很大，但點的總數很小時，要做序号轉化。
3.每次要小心題目裡0的情況。
*********************/


#define M 10005
vector<int> hnext[M];
int gender[M];
struct fpass
{
	int f1,f2;
};
bool cmp(struct fpass fa,struct fpass fb)
{
	if(fa.f1<fb.f1)
		return true;
	else if(fa.f1==fb.f1)
	{
		return fa.f2<fb.f2;
	}
	else return false;
}

int btos[M];
int stob[M];
int connect[305][305];
int main()
{
	int	n,m,p1,p2,s,e;
	int i,j;
	int snext,enext;
	scanf("%d%d",&n,&m);
	for(i=0;i<M;i++)
		btos[i]=stob[i]=-1;

	int bn=0;
	memset(connect,0,sizeof(connect));


	string sp1,sp2;
	
	while(m--){
		cin>>sp1>>sp2;
		if(sp1[0]=='-'){
			p1=atoi(sp1.substr(1).c_str());
			gender[p1]=0;
		}
		else{
			p1=atoi(sp1.c_str());
			gender[p1]=1;
		}
		
		if(sp2[0]=='-'){
			p2=atoi(sp2.substr(1).c_str());
			gender[p2]=0;
		}
		else{
			p2=atoi(sp2.c_str());
			gender[p2]=1;
		}
			
		if(btos[p1]==-1){
			btos[p1]=bn;
			stob[bn]=p1;
			bn++;
		}
		if(btos[p2]==-1){
			btos[p2]=bn;
			stob[bn]=p2;
			bn++;
		}
		hnext[p1].push_back(p2);
		hnext[p2].push_back(p1);
		connect[btos[p1]][btos[p2]]=1;
		connect[btos[p2]][btos[p1]]=1;
	}


	int k;
	scanf("%d",&k);
	vector<fpass> ans;
	fpass fp;
	while(k--){
		ans.clear();
		scanf("%d%d",&s,&e);
		
		if(s<0)
			s=s*(-1);
		if(e<0)
			e=e*(-1);
		
		//2次for循環查找B和C并判斷BC是否相鄰
		for(i=0;i<hnext[s].size();i++){
			snext = hnext[s][i];
		
			if(gender[snext]!=gender[s] || snext==e)
				continue;
			
			for(j=0;j<hnext[e].size();j++){
				enext = hnext[e][j];
				if(gender[enext]!=gender[e] || enext==s)
					continue;

				if(connect[btos[snext]][btos[enext]]){
					fp.f1=snext;
					fp.f2=enext;
					ans.push_back(fp);
				}
			}
		}
		printf("%d\n",ans.size());
		sort(ans.begin(),ans.end(),cmp);
		for(i=0;i<ans.size();i++){
			printf("%04d %04d\n",ans[i].f1,ans[i].f2);
		}
	}

}