Bzoj 3183(DFS)

bzoj 3183
Luogu免权限地址
裸搜索,根据生物学知识可得入度为0的结点是食物链开端,出度为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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i,j) memset(i,j,sizeof i)
using namespace std;
const int MAXN = 100000 + 5;
int n,m;
vector<int> G[MAXN];
int outd[MAXN], ino[MAXN];
int f[MAXN];
int ans = 0;
int dfs(int u)
{
int ret = 0;
if (outd[u]==0)
{
f[u] = 1;
return 1;
}
if (f[u]) return f[u];
for (int i=0;i<G[u].size();i++)
{
ret += dfs(G[u][i]);
}
f[u] = ret;
return ret;
}
int main()
{
scanf("%d%d", &n ,&m);
ms(outd, 0); ms(ino, 0);
for (int i=1;i<=m;i++)
{
int ai, bi;
scanf("%d%d", &ai, &bi);
G[ai].push_back(bi);
outd[ai]++; ino[bi]++;
}
ms(f, 0);
for (int i=1;i<=n;i++)
if (ino[i]==0&&outd[i]!=0)
{
ans += dfs(i);
}
printf("%d\n", ans);
return 0;
}

------ 本文结束 ------