030300606row.cpp

这是一个关于字典问题的源程序

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

class Unionfind
{
public:
   Unionfind(int n);
   ~Unionfind(){delete[]parent;delete[]root;}
   int Find(int e);
   void Union(int i,int j);
private:
   int *parent;
   bool *root;
};
Unionfind::Unionfind(int n)
{
	root=new bool[n];
	parent=new int[n];
	for(int e=0;e<n;e++)
	{
		parent[e]=1;
		root[e]=true;
	}
}
int Unionfind::Find(int e)
{
	int j=e;
	while(!root[j])
		j=parent[j];
	int f=e;
	while(f!=j)
	{

		int pf=parent[f];
		parent[f]=j;
		f=pf;
	}
	return j;
}
void Unionfind::Union(int i,int j)
{
	if(parent[i]<parent[j])
	{
		parent[j]+=parent[i];
		root[i]=false;
		parent[i]=j;
	}
	else
	{
		parent[i]+=parent[j];
		root[j]=false;
		parent[j]=i;
	}
}

void putin(int n,int a[])
{
	char x;
	for(int i=1;i<=n;i++)
	{
		in>>x;
		if(x>='a'&&x<='z')
			a[i]=(int)x-95;
		else
			if(x=='0')
				a[i]=0;
			else
				a[i]=1;
	}
}

int main()
{
	int n,k,j,r,p,q;
	in>>n;
	for(int i=0;i<n;i++)
	{
		in>>k;
		int **fx=new int*[k+2],*len=new int[k+2];
		fx[0]=new int[2];
		fx[1]=new int[2];
		for(j=2;j<=k+1;j++)
		{
			in>>len[j];
			fx[j]=new int[len[j]+1];
		}
		len[0]=1;
		len[1]=1;
		int name=2;
		for(j=2;j<=k+1;j++)
			for(r=1;r<=len[j];r++)
			{
				fx[j][r]=name;
				name++;
			}
		fx[0][1]=0;
		fx[1][1]=1;
		Unionfind U(name);
		int a,b;
		in>>a;
		int *left=new int[a+1];
		putin(a,left);
		in>>b;
		int *right=new int[b+1];
		putin(b,right);
		int c,d;
		j=r=1;
		p=q=1;
		while(j<=a&&r<=b)
		{
			while(p<=len[left[j]]&&q<=len[right[r]])
			{
				c=U.Find(fx[left[j]][p]);
				d=U.Find(fx[right[r]][q]);
			    if(c!=d)
				{
					U.Union(c,d);
					name--;
				}
				p++;
				q++;
			}
			if(p>len[left[j]])
			{   j++; p=1; }
			else
			{   r++; q=1; }
		}
		name-=2;
		if(j<a&&r>b||j>a&&r<b||j>a&&q<=len[right[r]]||r>b&&p<=len[left[j]]||U.Find(0)==U.Find(1))
			out<<-1<<endl;
		else
			out<<name<<endl;
		for(j=0;j<=k+1;j++)
			delete[]fx[j];
		delete[]fx;
		delete[]len;
		delete[]left;
		delete[]right;
	}
	return 0;
}