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);
		}
	}

}