[ABC292E] Transitivity 题解

FFTotoro · 2023-03-05 21:12:28 · 题解

本题需要使用简单的 BFS 算法。

注意到题目中的条件“若 a 到 b 有路径且 b 到 c 有路径，那么 a 和 c 必须有一条有向边连接”，其实可以转化一下——即“若 a 到 c 有路径，那么 a 和 c 必须有一条有向边连接”。

这样只用对于每个点 a，跑一遍 BFS，统计一下 a 能到达的点的数量，减去 a 连接的点数（因为题目中给出的图无重边，这个值即为 a 的出度）即为这个点的答案。最终答案即为所有点的答案之和。

放代码：

#include<bits/stdc++.h>
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,m,c=0; cin>>n>>m;
  vector<vector<int> > g(n);
  vector<int> d(n);
  for(int i=1;i<=m;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
  }
  for(int i=0;i<n;i++){
    vector<bool> b(n); // 打标记的数组，表示每个点是否被遍历过
    queue<int> q; q.emplace(i),b[i]=true;
    while(!q.empty()){
      int t=q.front(); q.pop();
      for(int j:g[t])if(!b[j])
        b[j]=true,q.emplace(j),d[i]++;
    } // 经典广搜
    c+=d[i]-g[i].size(); // d[i] 即为能到达的点的个数
  }
  cout<<c<<endl;
  return 0;
}