1965.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
int n;char s[10000];
int a[100],b[100],graph[100][100];
char ans[10000];
int ansc;
void getnum(char *ss)
{
	int i=0;
	n=0;
	while(ss[i]!='\0')
	{
		
		if(ss[i]>='0' && ss[i]<='9')
		{
			sscanf(s+i,"%d",&a[++n]);
		}
		while(ss[i]>='0' && ss[i]<='9')i++;
		if(ss[i]=='\0')break;
		i++;
	}
	n++;
}
void solve()
{
	int i,j,k;
	for(i=1;i<=n-2;i++)
	{
		for(j=1;j<=n;j++)if(b[j]==0)
		{
			int flag=1;
			for(k=i;k<=n-1;k++)
			{
				if(a[k]==j){flag=0;break;}
			}
			if(flag==1)break;
		}
		graph[a[i]][j]=1;graph[j][a[i]]=1;
		b[j]=1;
	}
	int x,y;
	for(i=1;i<=n;i++)if(b[i]==0)break;
	x=i;
	for(i++;i<=n;i++)if(b[i]==0)break;
	y=i;
	graph[x][y]=1;graph[y][x]=1;


}
void dfs(int t)
{
	b[t]=1;
	ans[ansc++]='(';
	char ss[10];
	sprintf(ss,"%d",t);
	sprintf(ans+ansc,"%s",ss);
	ansc+=strlen(ss);

	int i;	
	for(i=1;i<=n;i++)if(b[i]==0 && graph[t][i]==1)
	{
		ans[ansc++]=' ';
		dfs(i);
	}
	ans[ansc++]=')';

	
}


int main()
{
	int i,j,k;
	while(gets(s))
	{
		
		getnum(s);
		memset(graph,0,sizeof(graph));
		memset(b,0,sizeof(b));
		solve();
		ansc=0;
		memset(b,0,sizeof(b));
		dfs(n);
		ans[ansc]='\0';
		printf("%s\n",ans);
	}
	return 0;
}