传话游戏

时间限制: 1 Sec  内存限制: 128 MB
 

题目描述

有这样一个朋友网络，如果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。

 

样例输入

复制样例数据

4 6
1 2
2 3
4 1
3 1
1 3
2 3

样例输出

T
T
T
F

Tarjan模板题

Tarjan算法解析可以看：https://blog.csdn.net/qq_34374664/article/details/77488976

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m, tot;
int vis[1005], head[10005];
int dfn[1005], low[1005], st[1005], top, tim, ans[1005];

struct node
{
	int u, v, next;
}a[10005];

void add(int u, int v){
	a[tot].u = u, a[tot].v = v;
	a[tot].next = head[u], head[u] = tot++;
}

void Tarjan(int x){
	dfn[x] = low[x] = ++tim;
	vis[x] = 1;
	st[++top] = x;
	for (int i = head[x]; i != -1; i = a[i].next){
		int t = a[i].v;
		if(!dfn[t]){
			Tarjan(t);
			low[x] = min(low[x], low[t]);
		}else if(vis[t]){
			low[x] = min(low[x], dfn[t]);
		}
	}
	if(dfn[x] == low[x]){
		int num = 1;
		vis[x] = 0;
		while(st[top] != x){
			vis[st[top]] = 0;
			ans[st[top]] = 1;
			num++;
			top--;
		}
		top--;
		if(num == 1) ans[x] = 0;
		else ans[x] = 1;
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	memset(head, -1, sizeof(head));
	scanf("%d %d", &n, &m);
	int u, v;
	for (int i = 1; i <= m; i++) scanf("%d %d", &u, &v), add(u, v);
	for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
	for (int i = 1; i <= n; i++){
		if(!ans[i]) printf("F\n");
		else printf("T\n");
	}

	return 0;
}
/**/