AcWing 3250. 通信网络

题目描述

加反向边的技巧

在邻接表中声明两个链表数组$h1,h2$，分别表示正向边和反向边，在本题中枚举每一个点即可，在枚举某一点$u$时，对其进行两次$DFS$，分别是正向$DFS$和反向$DFS$能够到达的点，
用两个$bool$数组进行标记可到达的点即可。

时间复杂度

$O(NM)$，枚举每个点的时间为$N$，判断正向和反向所能到达的点数为$2\times M$

代码(C++)

#include 
#include 
#include 

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int h1[N], h2[N], e[M], ne[M], idx;
bool st1[N], st2[N];

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; i = ne[i])
	{
		int j = e[i];
		if(!st[j]) dfs(j, 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, 0, sizeof st1);
		memset(st2, 0, sizeof st2);
		dfs(i, h1, st1);
		dfs(i, h2, st2);
		
		int s = 0;
		for(int j = 1; j <= n; j ++)
			if(st1[j] || st2[j])
				s ++;
		if(s == n) res ++;
	}
	
	cout << res << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58