Description
You just finished your exam, you felt terrible because you might fail the exam. But your teacher was so kind that he might let you pass the lesson if you called him and begged for passing. Unfortunately, you didn’t have your teacher’s phone number! You began to ask whoever probably had the number, if they didn’t have, they would ask their classmates. Would you finally get the number?
Input
The first line contains an integer T (1 <= T <= 20), indicates the number of test cases.
For each test case, the first line is two positive integers, n (n <= 50), m (m <= 2000). n is the number of people who will appear in the problem, you are indexed as 1 and your teacher is indexed as n.
Then m lines follows, each line contains two integers x, y (1 <= x, y <= n), means x have the phone number of y.
Output
For each test case, if you could finally got your teacher’s number, output “^_^”, “T_T” the otherwise.
Sample Input
2
5 5
1 2
1 3
2 3
2 4
4 5
4 3
1 2
3 4
4 1
Sample Output
^_^
T_T
题目大意：
总共有n个人，其中有m条关系，以下n行中 x拥有y的电话，通过关系传递，1会不会有n的电话。
题解
通过Floyed算法思想，我这里用j作为for最外层作为两个关系联系起来的 “桥”，
所谓的“桥”代表关系过度的那个中间人，必然说a有b的电话，b有c的电话，那就说明b就是“桥”，通过将桥放到最外层，可以将所有之间存在间接关系都连接起来，最后判断是否1能直接到达n即可
参考代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m;
int book[1005][1005];
int main()
{int t;cin >> t;while (t--){memset(book, 0, sizeof(book));cin >> n >> m;for (int i = 0;i < m;i++){int a, b;cin >> a >> b;book[a][b] = 1;}for (int j = 1;j <= n;j++)//过桥{for (int i = 1;i <= n;i++){for (int k = 1;k <= n;k++){/*如果a与b有关系，且a与c有关系，则a与c有关系*/if (book[i][j] && book[j][k])book[i][k] = 1;}}}if (book[1][n])cout << "^_^" << endl;elsecout << "T_T" << endl;}
}