游客 注册 | 登录
中文 | En

1089 - 关系推断

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给你一些已经确定的元素之间的关系，请你判断是否能从这些元素关系中推断出其他的元素关系。

题目输入

输入的第一行是一个整数N，表示测试数据的组数。
每组输入首先是一个正整数m（m<=100），表示给定元素关系的个数。
接下来m行，每行一个元素关系，格式为：
元素1<元素2  或者  元素1>元素2
元素用一个大写字母表示，输入中不会包含冲突的关系。

题目输出

对于每组输入，第一行输出“Case d:”，d是测试数据的序号，从1开始。
接下来输出所有推断出的新的元素关系，按照字典序从小到大排序，格式为：
元素1<元素2
每个元素关系占一行，输入中给定的元素关系不要输出。
如果没有新的元素关系推断出来，则输出NONE。

输入/输出样例

输入格式

2
3
A<B
C>B
C<D
2
A<B
C<D

输出格式

Case 1:
A<C
A<D
B<D
Case 2:
NONE

C语言解答

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

int g[26][26],flag[26][26];

void floyd()
{
	int i,j,k;
	for(k=0;k<26;k++)
		for(i=0;i<26;i++)
			for(j=0;j<26;j++)
				if(flag[i][k]&&flag[k][j])
					flag[i][j]=1;
}

int main()
{
	int n,m,i,j,x,y,c=0,bj;
	char s[4];
	scanf("%d",&n);
	while(n--)
	{
		memset(g,0,sizeof(g));
		memset(flag,0,sizeof(flag));
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s",s);
			x=s[0]-'A';
			y=s[2]-'A';
			if(s[1]=='<')
			{
				g[x][y]=1;
				flag[x][y]=1;
			}
			else
			{
				g[y][x]=1;
				flag[y][x]=1;
			}
		}
		floyd();
		printf("Case %d:\n",++c);
		for(bj=i=0;i<26;i++)
			for(j=0;j<26;j++)
				if(!g[i][j]&&flag[i][j])
				{
					bj=1;
					printf("%c<%c\n",i+'A',j+'A');
				}
		if(!bj)
			printf("NONE\n");
	}
	return 0;
}

C++解答

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

int g[26][26],flag[26][26];

void floyd()
{
	int i,j,k;
	for(k=0;k<26;k++)
		for(i=0;i<26;i++)
			for(j=0;j<26;j++)
				if(flag[i][k]&&flag[k][j])
					flag[i][j]=1;
}

int main()
{
	int n,m,i,j,x,y,c=0,bj;
	char s[4];
	scanf("%d",&n);
	while(n--)
	{
		memset(g,0,sizeof(g));
		memset(flag,0,sizeof(flag));
		scanf("%d",&m);
		while(m--)
		{
			scanf("%s",s);
			x=s[0]-'A';
			y=s[2]-'A';
			if(s[1]=='<')
			{
				g[x][y]=1;
				flag[x][y]=1;
			}
			else
			{
				g[y][x]=1;
				flag[y][x]=1;
			}
		}
		floyd();
		printf("Case %d:\n",++c);
		for(bj=i=0;i<26;i++)
			for(j=0;j<26;j++)
				if(!g[i][j]&&flag[i][j])
				{
					bj=1;
					printf("%c<%c\n",i+'A',j+'A');
				}
		if(!bj)
			printf("NONE\n");
	}
	return 0;
}
请先登陆