传话游戏(求强联通分量)

分量)"/>

传话游戏(求强联通分量)

传话游戏

时间限制: 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算法解析可以看：

/**/
#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;
}
/**/