zoj2209.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <stdio.h>
#include <memory.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

map<string,int> da,db;
int an,bn,n;
char buff[100];
vector<string> sa,sb;
int ra[30],la[30],rb[30],lb[30];
int ca[30][30],cb[30][30];

bool input()
{
	scanf("%d",&n);
	if (n==0) return 0;
	int i,x,y;
	da.clear();
	memset(ra,0,sizeof(ra));
	memset(la,0,sizeof(la));
	sa.clear();
	memset(ca,0,sizeof(ca));
	an=0;
	for (i=0;i<n;++i)
	{
		scanf("%s",buff);
		if (da.count(buff)==0)
		{
			sa.push_back(buff);
			da[sa[an]]=an;
			++an;
		}
		x=da[buff];
		scanf("%s",buff);
		if (da.count(buff)==0)
		{
			sa.push_back(buff);
			da[sa[an]]=an;
			++an;
		}
		y=da[buff];
		++ra[x];
		++la[y];
		++ca[x][y];
	}
	db.clear();
	memset(rb,0,sizeof(rb));
	memset(lb,0,sizeof(lb));
	sb.clear();
	memset(cb,0,sizeof(cb));
	bn=0;
	for (i=0;i<n;++i)
	{
		scanf("%s",buff);
		if (db.count(buff)==0)
		{
			sb.push_back(buff);
			db[sb[bn]]=bn;
			++bn;
		}
		x=db[buff];
		scanf("%s",buff);
		if (db.count(buff)==0)
		{
			sb.push_back(buff);
			db[sb[bn]]=bn;
			++bn;
		}
		y=db[buff];
		++rb[x];
		++lb[y];
		++cb[x][y];
	}
	return 1;
}

int csd[30],usd[30];

bool dfs(const int &dep)
{
	if (dep==an) return 1;
	int i,j;
	bool flag;
	for (i=0;i<bn;++i)
		if (!usd[i]&&ra[dep]==rb[i]&&la[dep]==lb[i])
		{
			usd[i]=1;
			csd[dep]=i;
			flag=1;
			for (j=0;j<=dep&&flag;++j)
				if (ca[j][dep]!=cb[csd[j]][csd[dep]]||ca[dep][j]!=cb[csd[dep]][csd[j]]) flag=0;
			if (flag&&dfs(dep+1)) return 1;
			usd[i]=0;
		}
	return 0;
}

bool cmp(const int &a,const int &b)
{
	return sa[a]<sa[b];
}

int id[30];

void output()
{
	int i;
	for (i=0;i<an;++i)
		id[i]=i;
	sort(id,id+an,cmp);
	memset(usd,0,sizeof(usd));
	dfs(0);
	for (i=0;i<an;++i)
		printf("%s/%s\n",sa[id[i]].c_str(),sb[csd[id[i]]].c_str());
}

int main()
{
	int cs=0;
	while (input())
	{
		if (cs) printf("\n");
		++cs;
		output();
	}
	return 0;
}