题目描述
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
输入格式
第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。
输出格式
输出共N行，表示每个点能够到达的点的数量。
数据范围
1≤N,M≤30000
输入样例：
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
算法1
(暴力枚举)
从暴力开始吧。
就是bfs遍历各个点 再将能达到的点能达到的点再次加入。
结果是毫无悬念的tle了。
C++ 代码
#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<int> g[30010];
int n, m;
set<int> ss[30010];
void checkInner(set<int>& sInner, int p)
{
sInner.insert(p);
int count = 0;
for (int i = 0; i < g[p].size(); i++) {
if(sInner.count(g[p][i]) == 0){
checkInner(sInner, g[p][i]);
}
}
}
void check(int point)
{
for (int i = 0; i < g[point].size(); i++) {
if (ss[point].count(g[point][i]) == 0)
checkInner(ss[point],g[point][i]);
}
}
void solve()
{
for (int i = 1; i <= n; i++) {
check(i);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
solve();
for (int i = 1; i <= n; i++) {
cout << ss[i].size()+1 << endl;
}
return 0;
}
算法2
(再次暴力枚举)
在朴素的暴力枚举的时候 隐隐感觉使用拓扑排序后，BFS能有效的减少层级
而且反向搜索点的时候 后面搜索的点可以使用前面已经搜索了的点能达到的点记录
问题在于 使用已经搜索后的记录 会有重复的点，如何去重？ 我使用了set
结果这种想法也tle了
C++ 代码
// 3333333.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
vector<int> g[30010];
vector<int> copyg[30010];
int dIn[30010];
bitset<30010> f[30010];
int n, m;
/*
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
*/
void solve()
{
queue<int> q;
int i = 1;
for ( i = 1; i < n; i++) {
if (dIn[i] == 0) {
q.push(i);
}
}
for (int i = 0; i < 30010; i++) {
copyg[i] = g[i];
}
vector<int> ans;
while (q.size()) {
int point = q.front();
q.pop();
ans.push_back(point);
//抹掉该点 和该点发出的边
for (auto& e : g[point]) {
//减掉入度
dIn[e]--;
//如果入度为0 可以放入队列 进行下一次遍历
if (dIn[e] == 0)
q.push(e);
}
g[point].clear();
}
vector<set<int>> vss(n+10);
for (int i = ans.size() - 1; i >= 0; i--) {
int point = ans[i];
for (int j = 0; j < copyg[point].size(); j++) {
vss[point].insert(copyg[point][j]);
for (auto& e : vss[copyg[point][j]]) {
vss[point].insert(e);
}
}
}
for (int i = 1; i <= n; i++) {
cout << vss[i].size()+1 << endl;
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
g[a].push_back(b);
dIn[b]++;
}
solve();
}
算法2
(拓扑排序 压缩)
最后得出正确的解决方案是拓扑排序后使用bitset压缩
c++代码
// 3333333.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
vector<int> g[30010];
vector<int> copyg[30010];
int dIn[30010];
bitset<30010> f[30010];
int n, m;
/*
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
*/
void solve()
{
queue<int> q;
int i = 1;
for ( i = 1; i < n; i++) {
if (dIn[i] == 0) {
q.push(i);
}
}
for (int i = 0; i < 30010; i++) {
copyg[i] = g[i];
}
vector<int> ans;
while (q.size()) {
int point = q.front();
q.pop();
ans.push_back(point);
//抹掉该点 和该点发出的边
for (auto& e : g[point]) {
//减掉入度
dIn[e]--;
//如果入度为0 可以放入队列 进行下一次遍历
if (dIn[e] == 0)
q.push(e);
}
g[point].clear();
}
for (int i = ans.size() - 1; i >= 0; i--) {
int j = ans[i];
f[j][j] = 1;
for (int k = 0; k < copyg[j].size(); k++) {
f[j] |= f[copyg[j][k]];
}
}
for (int i = 1; i <= n; i++) {
cout << f[i].count() << endl;
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
g[a].push_back(b);
dIn[b]++;
}
solve();
}
