1270.cpp

acm-pku-1270 Following Orders 拓扑排序

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int count[27],link[27][27],visit[27],Len;
char save[30];

void deleteSpace(char str[])   
{   
	int i=0,j=0;   
	while(str[i]!='\0')   
	{   
		if(!isspace(str[i])) str[j++]=str[i];   
		i++;   
	}
	str[j]='\0';   
} 

void printfall(int n)
{
	int i,j;
	if(n==Len) { save[n]='\0'; printf("%s\n",save); return; }
	for(i=1;i<27;i++)
	{
		if(!visit[i]&&count[i]==1)
		{
			save[n]='a'+i-1;
			visit[i]=1;
			j=0; while(link[i][j]) { count[link[i][j]]--; j=link[i][j]; } 
			printfall(n+1);
			j=0; while(link[i][j]) { count[link[i][j]]++; j=link[i][j]; } 
			visit[i]=0;
		}
	}
}

int main()
{
	int i;
	char temp[53];
	while(1)
	{
		memset(visit,0,sizeof(int)*27);
		memset(count,0,sizeof(int)*27);
	    memset(temp,0,sizeof(char)*53);
		for(i=0;i<27;i++) link[i][0]=0;
		if((gets(temp))!=NULL);
		else  break; 
		deleteSpace(temp); 
		for(i=0;i<strlen(temp);i++)   count[temp[i]-'a'+1]++;
		Len=i;
		memset(temp,0,sizeof(char)*53);
		gets(temp); deleteSpace(temp);

		for(i=1;i<strlen(temp);i=i+2) 
		{
			link[temp[i-1]-'a'+1][temp[i]-'a'+1]=link[temp[i-1]-'a'+1][0];
			link[temp[i-1]-'a'+1][0]=temp[i]-'a'+1;
			count[temp[i]-'a'+1]++;
		}
		printfall(0);
		printf("\n");
	}
	return 0;
}