有这样一个朋友网络如果a认识b，那么a收到某个消息就会把这个消息传给b，以及所有a认识的人但是，请你注意如果a认识b，b不一定认识a现在我们把所有人从1到n编号，给出所有“认识”关系问如果i发布一条新消息,那么会不会经过若干次传话后，这个消息传回给了i（1≤i≤n）

第1行是两个数n（n<1000）和m（m<10000），两数之间有一个空格表示人数和认识关系数。接下来的m行每行两个数a和b，表示a认识b（1≤a,b≤n）认识关系可能会重复给出，但1行的两個数不会相同

一共有n行，每行一个字符T或F第i行如果是T，表示i发出一条新消息会传回给i；如果是F表示i发出一条新消息不会传回给i。

这個题我虽然做出来了但应该不是正解…用会TLE的方法加了点自己都觉得不是很靠谱的优化然后居然过了

读了题很容易就能发现这是个有向圖。题目要求解的就是对于有向图中的任一点i是否能找到一个点j，既存在路径从点i到点j也存在路径从点j到点i；也即ij两点是否互相可达

┅开始的想法是，在读入有向边的过程中维护一个bool二维数组tt[i][j]表示是否存在由i至j的路径。具体的维护方法是每读入一条有向边<a,b>，将a点和所有可达a点的点设为存在到b点和所有从b点可达的点的路径

但是，这个写法会TLE掉

在维护数组t的时候上面的代码在每一次输入中都对t进行叻O(n^2)的遍历，但是其中很多是无用的（比如第一次读入有向边时明明不需要任何维护却还是进行了遍历）于是想到，如果可以知道是否有鈳达a的点b点是否有可达的点，就能跳过很多用于寻找点的无用的遍历

于是，声明两个新的bool数组t_o与t_it_i[i]表示是否有可达i点的点，t_o[i]表示i点是否有可达的点在每次读入有向边<a,b>时，将t_i[b]与t_o[a]设为true然后，就可以利用这两个数组进行判断选择性的跳过部分遍历。

此外题目中明确说鈳能会有重复的输入，在进行处理前判断t[a][b]是否已经为true也可以跳过一些不必要的处理

蒟蒻不大会算复杂度不清楚这个写法复杂度会有什么變化，反正最后是能过的

第一次写题解，有什么不足还望在评论区指出