欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【CodeVS 1506】传话

程序员文章站 2022-05-27 16:22:37
...

【题目】

传送门

题目描述 Description

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

如果 aa 认识 bbbb 不一定认识 aa

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

输入描述 Input Description

第一行是 nnmm,表示人数和认识关系数。

接下来的 mm 行,每行两个数 aabb,表示 aa 认识 bb1a,bn1≤a, b≤n。认识关系可能会重复给出,但一行的两个数不会相同。

输出描述 Output Description

一共 nn 行,每行一个字符 TF。第 ii 行如果是 T,表示 ii 发出一条新消息会传回给 ii;如果是 F,表示 ii 发出一条新消息不会传回给 ii

样例输入 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

n1000n≤1000
1a,bn1≤a, b≤n


【分析】

应该可以算一道 TarjanTarjan 裸题了吧

对图进行缩点,如果一个点所在的连通块只有它一个点,就是 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;
}
相关标签: Tarjan