cogs 619. [金陵中学2007] 传话 Tarjan强连通分量
2024-09-06 14:08:49
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
很显然 这就是一道强联通分量 就是判断自己所在的那个强联通分量的大小是不是大于1
大于1 就是可以传回自己
加油哦
帅气的代码:
#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int n,m;
vector<int> v[maxn];
int dfn[maxn],low[maxn],belong[maxn],size[maxn],st[maxn],scc_cnt,cnt,tim;
bool bein[maxn];
void Tarjan(int rt){
dfn[rt]=low[rt]=++tim;
st[++cnt]=rt;
bein[rt]=true;
for(int i=;i<v[rt].size();i++){
int to=v[rt][i];
if(!dfn[to])//正向边
Tarjan(to),low[rt]=min(low[rt],low[to]);
else if(bein[to])//反向边
low[rt]=min(low[rt],dfn[to]);
}
if(dfn[rt]==low[rt]){
scc_cnt++;int k;
do {
k=st[cnt--];
belong[k]=scc_cnt;
bein[k]=false;
size[scc_cnt]++;
}while(k^rt);
}
}
int main(){
//freopen("messagez.in","r",stdin);freopen("messagez.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<m;i++){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
}
for(int i=;i<=n;i++)
if(!dfn[i])Tarjan(i);
for(int i=;i<=n;i++)
if(size[belong[i]]>)puts("T");
else puts("F");
return ;
}
最新文章
- Sql Server2005恢复备份数据库问题-Error:3154 3219
- MVC5 + EF6 + Bootstrap3 (8) HtmlHelper用法大全(上)
- Google Play支付校验
- Codeforces Round 190 div.2 322C 321A Ciel and Robot
- Google Chrome中的高性能网络 (三)
- HDU2056JAVA
- 对于百川SDK签名验证的问题
- 【转】MVP和MVC的区别
- jquery ui 笔记
- javascript 中 arguments.callee属性
- Chrome中java因过期而遭到阻止
- LoadRunner性能测试过程中报Error(-17998):Failed to get [param not passed in call] thread TLS entry.
- 【英国毕业原版】-《博尔顿大学毕业证书》Bolton一模一样原件
- 对HTML5标签的认识(三)
- Win7下emacs简单配置
- 重复造轮子,编写一个轻量级的异步写日志的实用工具类(LogAsyncWriter)
- Mysql加锁过程详解(4)-select for update/lock in share mode 对事务并发性影响
- Flannel配置详解
- 【转载】C# 中的委托和事件(详解:简单易懂的讲解)
- Delphi调用DLL中的接口