【BFS】ABC292 E - Transitivity

小咪咪 2024-03-23 14:43 8阅读 0赞

[E - Transitivity (atcoder.jp)][E - Transitivity _atcoder.jp]

![b00ee1dbbdc8443591674332d52a9480.png][]

![1d9a919c92e24d7b8d9b25760390918c.png][]

思路：

如果两个结点距离>=2，那么这两个点一定要加一条有向边

因此对每个点BFS统计答案即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    queue<int> q;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int n,m,u,v,tot=0,ans=0;
    int head[mxn],dis[mxn],vis[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    
    void bfs(int u){
    	memset(vis,0,sizeof(vis));
    	memset(dis,0x3f,sizeof(dis));
    	vis[u]=1;
    	dis[u]=0;
    	q.push(u);
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		if(dis[u]>=2) ans++;
    		for(int i=head[u];~i;i=edge[i].next){
    			if(dis[edge[i].to]>dis[u]+1){
    				dis[edge[i].to]=dis[u]+1;
    				q.push(edge[i].to);
    			}
    		}
    	}
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=n;i++){
    		head[i]=-1;
    	}
    }
    signed main(){
    	cin>>n>>m;
    	G_init();
    	for(int i=1;i<=m;i++){
    		cin>>u>>v;
    		add(u,v);
    	}
    	for(int i=1;i<=n;i++) bfs(i);
    	cout<<ans<<'\n';
    }

[E - Transitivity _atcoder.jp]: https://atcoder.jp/contests/abc292/tasks/abc292_e
[b00ee1dbbdc8443591674332d52a9480.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2981510dba764dd7bcd7cb680262734b.png
[1d9a919c92e24d7b8d9b25760390918c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/728c183c564f4aed9b2f05d23cfdc34d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 AtCoder Beginner Contest 296 E - Transition Game

[E - Transition Game (atcoder.jp)][E - Transition Game _atcoder.jp] 题意： ![7874049e4e0d

客官°小女子只卖身不卖艺/ 2024年03月24日 13:36/ 0 赞/ 14 阅读

相关【BFS】ABC292 E - Transitivity

[E - Transitivity (atcoder.jp)][E - Transitivity _atcoder.jp] ![b00ee1dbbdc844359167433

小咪咪/ 2024年03月23日 14:43/ 0 赞/ 9 阅读

相关 leetcode292. Nim 游戏

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5

短命女/ 2022年09月12日 02:49/ 0 赞/ 145 阅读

相关 leetcode-292.Nim Game

leetcode-292.Nim Game You are playing the following Nim Game with your friend: There

古城微笑少年丶/ 2022年07月27日 16:49/ 0 赞/ 122 阅读

相关 leetcode 292. Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on th

小鱼儿/ 2022年07月25日 15:44/ 0 赞/ 142 阅读

相关 292. Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on th

╰半橙微兮°/ 2022年07月15日 01:34/ 0 赞/ 103 阅读

相关 292. Nim Game

/ You are playing the following Nim Game with your friend: There is a heap of st

雨点打透心脏的1/2处/ 2022年06月09日 03:55/ 0 赞/ 154 阅读

相关 LeetCode292. Nim游戏

你和你的朋友，两个人一起玩 [Nim游戏][Nim]：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每

朴灿烈づ我的快乐病毒、/ 2022年05月23日 03:51/ 0 赞/ 156 阅读

相关 leetcode:292. Nim游戏

题目: 你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每

朱雀/ 2022年03月02日 13:06/ 0 赞/ 170 阅读

相关 [leetcode-292-Nim Game]

You are playing the following Nim Game with your friend: There is a heap of stones on th

逃离我推掉我的手/ 2022年01月06日 11:17/ 0 赞/ 204 阅读