题目描述 Description
一个朋友网络，如果a认识b，那么如果a第一次收到某个消息，那么会把这个消息传给b，以及所有a认识的人。
如果a认识b，b不一定认识a。
所有人从1到n编号，给出所有“认识”关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了i，1<=i<=n。
输入描述 Input Description
第一行是n和m，表示人数和认识关系数。
接下来的m行，每行两个数a和b，表示a认识b。1<=a, b<=n。认识关系可能会重复给出，但一行的两个数不会相同。
输出描述 Output Description
一共n行，每行一个字符T或F。第i行如果是T，表示i发出一条新消息会传回给i；如果是F，表示i发出一条新消息不会传回给i。
样例输入 Sample Input
4 6
1 2
2 3
4 1
3 1
1 3
2 3
样例输出 Sample Output
T
T
T
F
数据范围及提示 Data Size & Hint
n<=1000
1<=a, b<=n
分类标签 Tags 点此展开
思路：
判断每个人的话能不能传回自己
用搜索就很容易ac
但是今天的主要练习是tarjan
（Q：tarjan是什么？）
（A:不会面壁去，不懂百度去）
用tarjan求出所有的环
然后把每个点就标记一下
每个标记指向这个点所属的环
如果这个点所指向的环的元素个数大于1（成环能回到自己）则输出T
否则(环的元素个数为1，只有他自己)输出F
来，上代码:
#include<cstdio>
#include<iostream> using namespace std; struct node {
int from,to,next;
};
struct node edge[]; int n,m,num=,head[],dfn[],low[];
int tarjan_dfn=,tarjan_loop=,loop[];
int stack[],stack_top=,belong[]; bool map[][],flag[]; char ch; inline void edge_add(int from,int to)
{
num++;
edge[num].to=to;
edge[num].from=from;
edge[num].next=head[from];
head[from]=num;
} inline void qread(int &x)
{
x=;ch=getchar();
while(ch>''||ch<'') ch=getchar();
while(ch<=''&&ch>=''){x=x*+(int)(ch-'');ch=getchar();}
} void tarjan_forloop(int serc)
{
tarjan_dfn++;
dfn[serc]=tarjan_dfn;
low[serc]=tarjan_dfn;
stack_top++;
stack[stack_top]=serc;
flag[serc]=true;
for(int i=head[serc];i!=;i=edge[i].next)
{
if(!dfn[edge[i].to])
{
tarjan_forloop(edge[i].to);
low[serc]=min(low[serc],low[edge[i].to]);
}
else if(flag[edge[i].to]) low[serc]=min(low[serc],low[edge[i].to]);
}
if(low[serc]==dfn[serc])
{
tarjan_loop++;
while(stack[stack_top]!=serc)
{
loop[tarjan_loop]++;
belong[stack[stack_top]]=tarjan_loop;
flag[stack[stack_top]]=false;
stack_top--;
}
loop[tarjan_loop]++;
belong[stack[stack_top]]=tarjan_loop;
flag[stack[stack_top]]=false;
stack_top--;
}
} int main()
{
int from,to;
qread(n),qread(m);
for(int i=;i<=m;i++)
{
qread(from),qread(to);
if(map[from][to]) continue;
map[from][to]=true;
edge_add(from,to);
}
for(int i=;i<=n;i++) if(!dfn[i]) tarjan_forloop(i);
for(int i=;i<=n;i++)
{
if(loop[belong[i]]>)
{
putchar('T');
putchar('\n');
}
else
{
putchar('F');
putchar('\n');
}
}
return ;
}