「CH2101」可達性統計 解題報告

CH2101 可達性統計

描述

給定一張N個點M條邊的有向無環圖，分別統計從每個點出發能夠到達的點的數量。N,M≤30000。

輸入格式

第一行兩個整數N,M，接下來M行每行兩個整數x,y，表示從x到y的一條有向邊。

輸出格式

共N行，表示每個點能夠到達的點的數量。

樣例輸入

10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

樣例輸出

1
6
3
3
2
1
1
1
1
1

---

思路

我們可以利用記憶化搜索，對于每個點，記錄它能到達的點的集合。

至于怎么記錄這個集合，我們采用bitset

bitset<MAXN> f[MAXN];

由于bitset十分省內存，30000大小就占用30000bit，不用擔心炸空間。

還有，bitset支持位運算！你可以當做一個二進制數來操作，也可以當做一個bool數組，還支持各種神奇函數，十分強大。

bitset<MAXN> a, b;
a[1] = 1;//當做bool數組~
b[2] = 1;
a = a | b;//支持位運算~
printf("%llu\n", a.count());//統計1的個數~ 返回值是unsigned long long類型的

搜索過程十分簡單，差不多是一個記憶化搜索模板。

P.S. 當然你也可以拓撲序DP

代碼

#include<bits/stdc++.h>
using namespace std;
#define MAXN 30005
#define MAXM 30005
#define bs bitset<30005>int n, m;
int hd[MAXN], nxt[MAXM], to[MAXM], tot;
bs f[MAXN];
int x, y;inline void Add( int x, int y ){ nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y; }void DFS( int x ){if ( f[x].any() ) return;f[x][x] = 1;for ( int i = hd[x]; i; i = nxt[i] )f[x] |= ( DFS( to[i] ), f[to[i]] );
}int main(){scanf( "%d%d", &n, &m );for ( int i = 1; i <= m; ++i ){ scanf( "%d%d", &x, &y ); Add( x, y ); }for ( int i = 1; i <= n; ++i ) printf( "%llu\n", ( DFS(i), f[i].count() ) );return 0;
}