E - Transitivity Editorial by en_translator
The optimal strategy is to repeatedly find distinct vertices \(a\), \(b\) and \(c\) such that a directed edge from vertex \(a\) to vertex \(b\) and another from vertex \(b\) to vertex \(c\) exist but one from vertex \(a\) to vertex \(c\) doesn’t, and add a directed edge from vertex \(a\) to vertex \(c\); however, it is a bit difficult to finish it within the execution time limit.
In fact, a directed edge from vertex \(x\) exists in the final graph if and only if it goes to a vertex reachable from vertex \(x\) in the original graph (except for \(x\) itself).
Proof
The simulation described above adds a directed edge from $x$ to $y$ while there is a vertex $y$ whose distance from a vertex $x$ is two. This operation does not change the vertices reachable from $x$. Also, when the operation is no longer possible, there is no vertex whose distance from $x$ is two, so the edges going out from $x$ in the final state all go to the vertices reachable from $x$ in the original state.Therefore, it is sufficient to count the reachable vertices from each vertex in the original graph with BFS (Breadth-First Search) or DFS (Depth-First Search). Since one can perform BFS or DFS from a vertex in an \(\mathrm{O}(M)\) time, the total complexity is \(\mathrm{O}(NM)\).
Sample code (C++, with BFS)
#include <bits/stdc++.h>
using namespace std;
int main() {
int N,M;
cin>>N>>M;
vector<vector<int>> E(N);
for(int i=0;i<M;i++){
int u,v;
cin>>u>>v;
E[u-1].push_back(v-1);
}
int ans = 0;
for(int i=0;i<N;i++){
vector<bool> f(N,false);
f[i] = true;
queue<int> Q;
Q.push(i);
while(Q.size()>0){
int x = Q.front();
Q.pop();
for(int j=0;j<E[x].size();j++){
int y = E[x][j];
if(f[y])continue;
f[y] = true;
Q.push(y);
ans++;
}
}
}
ans -= M;
cout<<ans<<endl;
return 0;
}
posted:
last update: