题目链接： http://acm.zzuli.edu.cn/problem.php?id=1676
题目描述
新学年开学了，学校又迎来了一批新同学，已知部分同学之间的身高关系，请列出可推断出的同学之间的身高关系。
输入
第一行是一个整数n，表示有n组测试数据。
每组测试数据第一行是一个正整数m（m<=100），表示已知同学之间的身高关系有m组，身高关系没有相等的情况。
接下来输入m行身高关系，每位同学用一个大写字母表示。
输出
对于第d组测试数据，首先输出“Case d:”，d从1开始。
输出能够推断出的同学之间的身高关系，按字母的字典序输出。
已知条件中的身高关系不要输出。
如果推断不出任何新的身高关系，输出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
解法1：DFS
#include <bits/stdc++.h>
using namespace std;
bool vis[][];
int m;
vector<int>V[];
struct node
{
int a, b;
} q[];
bool cmp(node x, node y)
{
if(x.a == y.a) return x.b < y.b;
return x.a < y.a;
}
void dfs(int x, int y)
{
for(int i = ; i < V[y].size(); i++)
{
int v = V[y][i];
if(!vis[x][v])
{
q[++m].a = x;
q[m].b = v;
}
dfs(x, v);
}
}
int main()
{
int t, n, i;
cin>>t;
int cas = ;
while(t--)
{
scanf("%d", &n);
for(i = ; i < ; i++) V[i].clear();
memset(vis, , sizeof vis);
m = ;
while(n--)
{
char s[];
scanf("%s", s);
int a = s[] - 'A';
int b = s[] - 'A';
if(s[] == '<') V[a].push_back(b), vis[a][b] = ;
else V[b].push_back(a), vis[b][a] = ;
}
printf("Case %d:\n", ++cas);
for(i = ; i < ; i++)
dfs(i, i);
sort(q+, q++m, cmp);
for(i = ; i <= m; i++)
printf("%c<%c\n", q[i].a+'A', q[i].b+'A');
if(!m) puts("NONE");
}
return ;
}
解法2：BFS
#include <bits/stdc++.h>
using namespace std;
bool vis[][];
int m;
vector<int>V[];
struct node
{
int a, b;
} q[];
bool cmp(node x, node y)
{
if(x.a == y.a) return x.b < y.b;
return x.a < y.a;
}
int main()
{
int t, n, i;
cin>>t;
int cas = ;
while(t--)
{
scanf("%d", &n);
for(i = ; i < ; i++) V[i].clear();
memset(vis, , sizeof vis);
m = ;
while(n--)
{
char s[];
scanf("%s", s);
int a = s[] - 'A';
int b = s[] - 'A';
if(s[] == '<') V[a].push_back(b), vis[a][b] = ;
else V[b].push_back(a), vis[b][a] = ;
}
printf("Case %d:\n", ++cas);
for(i = ; i < ; i++)
{
queue<int>Q;
Q.push(i);
while(!Q.empty())
{
int t = Q.front();
Q.pop();
for(int j = ; j < V[t].size(); j++)
{
int v = V[t][j];
if(!vis[i][v])
{
q[++m].a = i;
q[m].b = v;
}
Q.push(v);
}
}
}
sort(q+, q++m, cmp);
for(i = ; i <= m; i++)
printf("%c<%c\n", q[i].a+'A', q[i].b+'A');
if(!m) puts("NONE");
}
return ;
}
解法3：并查集
#include <bits/stdc++.h>
using namespace std;
int vis[][], par[];
int main()
{
int n, m, i, j;
char s[];
cin>>n;
int cas = ;
while(n--)
{
scanf("%d", &m);
for(i = ; i < ; i++) par[i] = i;
memset(vis, , sizeof vis);
while(m--)
{
scanf("%s", s);
int a = s[] - 'A';
int b = s[] - 'A';
if(s[] == '<')
par[a] = b, vis[a][b] = ;
else
par[b] = a, vis[b][a] = ;
}
printf("Case %d:\n", ++cas);
m = ;
for(i = ; i < ; i++)
{
for(j = ; j < ; j++)
{
int k = i;
if(i == j) continue;
while()
{
k = par[k];
if(k == j && !vis[i][j])
{
printf("%c<%c\n", i+'A', j+'A');
m++;
}
if(k == par[k]) break;
}
}
}
if(!m) puts("NONE");
}
return ;
}
解法4：floyd
#include <bits/stdc++.h>
using namespace std;
int mp[][];
int main()
{
int t, n;
cin>>t;
int cas = ;
while(t--)
{
scanf("%d", &n);
memset(mp, , sizeof mp);
bool f = false;
while(n--)
{
char s[];
scanf("%s", s);
int a = s[] - 'A';
int b = s[] - 'A';
if(s[] == '<') mp[a][b] = ;
else mp[b][a] = ;
}
printf("Case %d:\n", ++cas);
for(int k = ; k < ; k++)
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
if(mp[i][k] && mp[k][j] && !mp[i][j])
mp[i][j] = , f = true;
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
if(mp[i][j] == )
printf("%c<%c\n", i+'A', j+'A');
if(!f) puts("NONE");
}
return ;
}