AcWing 3250. 通信网络
原题链接
中等
作者:
把这题Ac了
,
2024-12-01 21:01:38
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010,M = 10010;
int h[N],e[M],ne[M],pot[N][N],st[N],idx;
int n,m;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
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);
}
for(int i = 1;i <= n;i++){
queue<int> q;
memset(st,0,sizeof st);
q.push(i);st[i] = 1;
while(q.size()){
int t = q.front();
q.pop();
for(int i = h[t];i != -1;i = ne[i]){
int k = e[i];
if(!st[k]) q.push(k);st[k] = 1;
}
}
for(int j = 1;j <= n;j++){
if(st[j]) pot[i][j] = pot[j][i] = 1;
}
}
int res = 0;
for(int i = 1;i <= n;i++){
int flag = 1;
for(int j = 1;j <= n;j++){
if(!pot[i][j]){
flag = 0;
break;
}
}
if(flag) res++;
}
cout << res << endl;
return 0;
}