AcWing 3220. 高速公路
原题链接
中等
作者:
把这题Ac了
,
2024-11-25 15:46:05
,
所有人可见
,
阅读 2
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010,M = 1e4 + 10;
typedef pair<int,int> PII;
int h[N],e[M],ne[M],idx;
int g[N][N];
queue<PII> q;
int n,m;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void bfs(){
while(q.size()){
auto t = q.front();
q.pop();
int u = t.first,v = t.second;
for(int i = h[v];i != -1;i = ne[i]){
int j = e[i];
if(g[u][j]) continue;
g[u][j] = 1;
q.push({u,j});
}
}
}
int main(){
memset(h,-1,sizeof h);
cin >> n >> m;
for(int i = 0;i < m;i++){
int a,b;
cin >> a >> b;
add(a,b);
q.push({a,b});
}
bfs();
int res = 0;
for(int i = 1;i <= n;i++){
for(int j = 1;j < i;j++){
if(g[i][j] && g[j][i]) res++;
}
}
cout << res << endl;
return 0;
}