1001. [WZOI2011 S3] 消息传递
★★ 输入文件：messagew.in 输出文件：messagew.out 简单对比
时间限制：1 s 内存限制：128 MB
tarjan求强连通分量，判断该点所在的强连通分量中的点的个数，若该点所在的强连通分量里的点的个数多于一个则说明出现了环，那么就会自己传递的信息再次传给自己、、
代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 210000 using namespace std; bool vis[N]; int n,m,x,y,tot,sum,tim,top; int dfn[N],low[N],ans[N],head[N],stack[N],belong[N]; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}return x*f; } struct Edge {int to,from,next; }edge[N]; int add(int x,int y) {tot++;edge[tot].to=y;edge[tot].next=head[x];head[x]=tot; } int tarjan(int now) {dfn[now]=low[now]=++tim;stack[++top]=now,vis[now]=true;for(int i=head[now];i;i=edge[i].next){int t=edge[i].to;if(vis[t]) low[now]=min(dfn[t],low[now]);else if(!dfn[t]) tarjan(t),low[now]=min(low[now],low[t]);}if(dfn[now]==low[now]){sum++;belong[now]=sum;ans[sum]++;for(;stack[top]!=now;top--){int x=stack[top];vis[x]=false;belong[x]=sum,ans[sum]++;}top--,vis[now]=false;} } int main() {freopen("messagew.in","r",stdin);freopen("messagew.out","w",stdout);n=read(),m=read();for(int i=1;i<=m;i++)x=read(),y=read(),add(x,y); for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int i=1;i<=n;i++)if(ans[belong[i]]>1) printf("T\n");else printf("F\n");return 0; }
