2007 NPSC G. 丁丁共和國
作法:DFS
找端點作DFS搜尋
/************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
short int map[2001][50]={0},flag[2001]={0},max=0,maptop[2001]={0};
void DFS(int now,int time,int top)
{
if(time>max) max=time;
int a,b;
for(a=0;a<maptop[now];a++)
if(flag[map[now][a]]==0)
{
flag[map[now][a]]=1;
DFS(map[now][a],time+1,top);
flag[map[now][a]]=0;
}
}
main()
{
int n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int a,b,c,start[2001]={0},top=0;
char xx[101],yy[101],name[2001][50]={0};
while(1)
{
scanf("%s %s",xx,yy);
if(strlen(xx)==1&&xx[0]=='=') break;
int a,b,c,m=strlen(xx),flagx,flagy,x[50]={0},y[50]={0};
for(a=0;a<m;a++) x[a]=xx[a];
for(b=0;b<top;b++)
{
for(a=0;a<50;a++)
if(x[a]!=name[b][a]) break;
if(a==50) {flagx=b;break;}
}
if(b==top)
{
for(a=0;a<m;a++)
name[top][a]=x[a];
flagx=top;top++;
}
m=strlen(yy);
for(a=0;a<m;a++) y[a]=yy[a];
for(b=0;b<top;b++)
{
for(a=0;a<50;a++)
if(y[a]!=name[b][a]) break;
if(a==50) {flagy=b;break;}
}
if(b==top)
{
for(a=0;a<m;a++)
name[top][a]=y[a];
flagy=top;top++;
}
map[flagx][maptop[flagx]]=flagy;
maptop[flagx]++;
map[flagy][maptop[flagy]]=flagx;
maptop[flagy]++;
start[flagy]++;
start[flagx]++;
}
max=0;
for(a=0;a<n;a++)
if(start[a]==1)
{
flag[a]=1;
DFS(a,0,n);
flag[a]=0;
}
printf("%d\n",max);
for(a=0;a<=n;a++)
maptop[a]=0;
}
return 0;
}
下一篇:2006 NPSC D. 水之都