TLE+WA了一晚上，整个人都不好了…最后居然是数组开小了…EXM？不是1000么… 哎，本来想刷个水题，结果一晚上就这么浪费了…
万恶的黑世界的大门
题目描述 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
这个题的思路很好想，就是找环，如果在环中就是T,不在环中就是F。 这是个dfs练习题，然而我选择用Tarjan水掉（话说Tarjan不就是dfs么）… Tarjan中的cnt2是记录一个环的长度，ans[scc[u]]就是代表着u这个节点所在的环的长度。然后做法就显而易见啦~(≧▽≦)/~
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; int n,m; const int MAXN=10000+10; int first[MAXN],nxt[MAXN<<1]; struct edge{ int from,to; }es[MAXN<<1]; int tot=0; void build(int ff,int tt) { es[++tot]=(edge){ff,tt}; nxt[tot]=first[ff]; first[ff]=tot; } int tim=0,cnt=0,ans[MAXN]; int dfn[MAXN],low[MAXN],scc[MAXN]; stack<int>s; void dfs(int now) { dfn[now]=low[now]=++tim; s.push(now); for(int i=first[now];i!=-1;i=nxt[i]) { int v=es[i].to; if(!dfn[v]) { dfs(v); low[now]=min(low[now],low[v]); } else if(!scc[v]) low[now]=min(low[now],dfn[v]); } if(low[now]==dfn[now]) { int cnt2=0; cnt++; while(true) { int x=s.top(); s.pop(); cnt2++; scc[x]=cnt; ans[scc[x]]=cnt2; if(x==now) break; } } } int main() { memset(first,-1,sizeof(first)); int ff,tt; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&ff,&tt); build(ff,tt); } for(int i=1;i<=n;i++) { if(!dfn[i]) dfs(i); } /*for(int i=1;i<=n;i++) if(scc[i]) cout<<scc[i]<<endl;*/ for(int i=1;i<=n;i++) { if(ans[scc[i]]>1) puts("T"); else puts("F"); } return 0; } /* 4 6 1 2 2 3 4 1 3 1 1 3 2 3 */