首页 > 代码库 > COGS 619. [金陵中学2007] 传话
COGS 619. [金陵中学2007] 传话
★☆ 输入文件：messagez.in 输出文件：messagez.out 简单对比
时间限制：1 s 内存限制：128 MB
[问题描述]
兴趣小组的同学来自各个学校，为了增加友谊，晚会上又进行了一个传话游戏，如果 a 认识 b ，那么 a 收到某个消息，就会把这个消息传给 b ，以及所有 a 认识的人。
如果 a 认识 b ， b 不一定认识 a 。
所有人从 1 到 n 编号，给出所有“认识”关系，问如果 i 发布一条新消息，那么会不会经过若干次传话后，这个消息传回给了 i ， 1<=i<=n 。
[输入文件]
输入文件 message.in 中的第一行是两个数 n(n<1000) 和 m(m<10000) ，两数之间有一个空格，表示人数和认识关系数。
接下来的 m 行，每行两个数 a 和 b ，表示 a 认识 b 。 1<=a, b<=n 。认识关系可能会重复给出，但一行的两个数不会相同。
[输出文件]
输出文件 message.out 中一共有 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 模板题
屠龙宝刀点击就送
#include <ctype.h>#include <cstdio>#define N 2000struct node{ int next,to; node (int next=0,int to=0): next(next),to(to){}}edge[N<<1];int min(int a,int b){ return a>b?b:a;}int ok[N],col[N],sumcol,n,cnt,m,head[N<<1],dfn[N],stack[N],top,tm,low[N];bool vis[N],instack[N];void read(int &x){ x=0;bool f=0; char ch=getchar(); while(!isdigit(ch)) { if(ch==‘-‘) f=1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-‘0‘; ch=getchar(); } x=f?(~x)+1:x;}void add(int x,int y){ edge[++cnt]=node(head[x],y); head[x]=cnt;}void dfs(int now){ dfn[now]=low[now]=++tm; instack[now]=1; stack[++top]=now; vis[now]=1; for(int i=head[now];i;i=edge[i].next) { int v=edge[i].to; if(instack[v]) low[now]=min(low[now],dfn[v]); else if(!vis[v]) { dfs(v); low[now]=min(low[now],low[v]); } } if(low[now]==dfn[now]) { sumcol++; int tot=0,k=0; do { tot++; k=stack[top--]; ok[k]=1; instack[k]=0; col[k]=sumcol; }while(k!=now); if(tot==1) ok[k]=0; }}int main(){ freopen("messagez.in","r",stdin); freopen("messagez.out","w",stdout); read(n);read(m); for(int x,y;m--;) { read(x);read(y); add(x,y); } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); for(int i=1;i<=n;i++) if(ok[i]) printf("T\n"); else printf("F\n"); return 0;}
COGS 619. [金陵中学2007] 传话
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。