【CodeVS 1506】传话

【题目】

传送门

题目描述 Description

一个朋友网络，如果 $a$a 认识 $b$b，那么如果 $a$a 第一次收到某个消息，那么会把这个消息传给 $b$b，以及所有 $a$a 认识的人。

如果 $a$a 认识 $b$b，$b$b 不一定认识 $a$a。

所有人从 $1$1 到 $n$n 编号，给出所有"认识"关系，问如果i发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了 $i$i，$1≤i≤n$1≤i≤n。

输入描述 Input Description

第一行是 $n$n 和 $m$m，表示人数和认识关系数。

接下来的 $m$m 行，每行两个数 $a$a 和 $b$b，表示 $a$a 认识 $b$b。$1≤a, b≤n$1≤a,b≤n。认识关系可能会重复给出，但一行的两个数不会相同。

输出描述 Output Description

一共 $n$n 行，每行一个字符 T 或 F。第 $i$i 行如果是 T，表示 $i$i 发出一条新消息会传回给 $i$i；如果是 F，表示 $i$i 发出一条新消息不会传回给 $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$n≤1000
$1≤a, b≤n$1≤a,b≤n

【分析】

应该可以算一道 $Tarjan$Tarjan 裸题了吧

对图进行缩点，如果一个点所在的连通块只有它一个点，就是 F；否则是 T

还是非常简单的吧

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1005
#define M 100005
using namespace std;
int n,m,t,now,top,sum;
int first[N],v[M],nxt[M];
int id[N],dfn[N],low[N],sta[N],num[N];
bool insta[N];
void add(int x,int y)
{
	t++;
	nxt[t]=first[x];
	first[x]=t;
	v[t]=y;
}
void Tarjan(int x)
{
	int i,j;
	dfn[x]=low[x]=++now;
	sta[++top]=x,insta[x]=true;
	for(i=first[x];i;i=nxt[i])
	{
		j=v[i];
		if(!dfn[j])
		{
			Tarjan(j);
			low[x]=min(low[x],low[j]);
		}
		else  if(insta[j])
		  low[x]=min(low[x],dfn[j]);
	}
	if(dfn[x]==low[x])
	{
		sum++;
		do
		{
			i=sta[top--];
			id[i]=sum;
			num[sum]++;
			insta[i]=false;
		}while(i!=x);
	}
}
int main()
{
	int x,y,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(i=1;i<=n;++i)
	{
		if(!dfn[i])
		  Tarjan(i);
		if(num[id[i]]>1)  puts("T");
		else  puts("F");
	}
	return 0;
}