1001关系推断

Description

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

Input

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

Output

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

Sample Input 

23A<BC>BC<D2A<BC<D
Sample Output
Case 1:A<CA<DB<DCase 2:NONE
分析：比赛的时候没能将这个题和图的知识联系起来，所以思路完全错误。百度之后发现就是一个简单的有向图问题。    元素1<元素2 或 元素2>元素1，表示从元素1到元素2有一条通路，以此类推，构成一个有向无环图。参考代码：
#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<string>#include<algorithm>#include<stack>#include<queue>#include<vector>#include<map>using namespace std;const int maxn = 30;int m;int g[maxn][maxn];//g[i][j]为1表示结点i+'A'到结点j+'A'直接可达int flag[maxn][maxn];//标记 值为1表示题目给出的关系 为0表示推理出来的关系int main(){    int T;    scanf("%d",&T);    int cnt = 1;    while( T--)    {        memset(g,0,sizeof(g));        memset(flag,0,sizeof(flag));        scanf("%d",&m);        for( int i = 1; i <= m; i++)        {            char s[5];            scanf("%s",s);            int u = s[0]-'A';            int v = s[2]-'A';            if( s[1] == '<')            {                g[u][v] = 1;                flag[u][v] = 1;            }            else            {                g[v][u] = 1;                flag[v][u] = 1;            }        }        for( int i = 0; i < maxn; i++)            for( int j = 0; j < maxn; j++)                for( int k = 0; k < maxn; k++)                    if( g[i][j] && g[j][k])                        g[i][k] = 1;        PRintf("Case %d:/n",cnt++);        int tmp = 1;        for( int i = 0; i < maxn; i++)            for( int j = 0; j < maxn; j++)                if( g[i][j] && !flag[i][j])                {                    printf("%c<%c/n",i+'A',j+'A');                    tmp = 0;                }        if( tmp)            printf("NONE/n");    }    return 0;}