201709-4 通信网络

思路:

应该要将题目进行转化,转化为平时可以理解的形式。这里就是说求所有这样的点,其他点要么可以访问他,要么可以被他访问到,也就是说用两种边,一种是正向的,一种是反向的,然后dfs就行了。

代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 20005;
int h1[N], h2[N], e[M], ne[M], idx;
bool st1[N], st2[N];
int n,m;
void add(int h[], int a, int b){
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int h[], bool st[]){
	st[u] = true;
	for(int i = h[u]; i != -1; i = ne[i]){
		int v = e[i];
		if(!st[v])dfs(v, h, st);
	}
}
int main(){
	cin>>n>>m;
	memset(h1, -1, sizeof(h1));
	memset(h2, -1, sizeof(h2));
	while(m--){
		int a,b;
		cin>>a>>b;
		add(h1, a, b);
		add(h2, b, a);
	}
	int res = 0;
	for(int i = 1;i<=n;i++){
		memset(st1, false, sizeof(st1));
		memset(st2, false, sizeof(st2));
		dfs(i, h1, st1);
		dfs(i, h2, st2);
		int cnt = 0;
		for(int j = 1;j<=n;j++){
			if(st1[j] || st2[j]){
				cnt++;
			}
		}
		if(cnt == n){
			res++;
		}
	}
	cout<<res;
}

上一篇:Ker f 是 G 的正规子群的完整证明


下一篇:使用jmeter监控服务器CPU