当前位置:网站首页>AcWing164. 可达性统计(拓扑排序+bitset)
AcWing164. 可达性统计(拓扑排序+bitset)
2022-07-05 00:02:00 【eva_can(not)survive】
164. 可达性统计 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/166/第一次用到bitset真是一个神奇的容器啊,让我们计算子集非常方便。
这个题也直接给出了是有个DAG所以我们可以直接求拓扑序列,然后倒序遍历将其每个点能触及到的状态记录。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;
int ver[MAXN];
int head[MAXN];
int nxt[MAXN];
int cnt;
int in[MAXN];
int tuop[MAXN];
int cnt1;
void add(int x, int y) {
ver[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
in[y]++;
}
int n, m;
const int N = 3e4 + 5;
bitset<N> rec[N];
void topsort() {
queue<int> q;
map<int, int> mp;
for (int i = 1; i <= n; i++) {
if (in[i])
continue;
q.push(i);
}
while (!q.empty()) {
int t = q.front();
q.pop();
tuop[++cnt1] = t;
for (int i = head[t]; i; i = nxt[i]) {
int v = ver[i];
in[v]--;
if (!in[v])
q.push(v);
}
}
}
int main() {
scanf("%d %d", &n, &m);
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
topsort();
for (int i = n; i >= 1; i--) {
int j = tuop[i];
rec[j][j] = 1;
for (int k = head[j]; k; k = nxt[k]) {
int v = ver[k];
rec[j] |= rec[v];
}
}
for (int i = 1; i <= n; i++) {
printf("%d\n", rec[i].count());
}
return 0;
}
边栏推荐
- 快解析——好用的内网安全软件
- Basic points of the game setup of the points mall
- Parsing of XML
- Application of multi loop instrument in base station "switching to direct"
- Design of emergency lighting evacuation indication system for urban rail transit station
- 企业公司项目开发好一部分基础功能,重要的事保存到线上第一a
- How to do the project of computer remote company in foreign Internet?
- ICML 2022 | 3dlinker: e (3) equal variation self encoder for molecular link design
- 机器人强化学习——Learning Synergies between Pushing and Grasping with Self-supervised DRL (2018)
- Is the account opening link of Huatai Securities with low commission safe?
猜你喜欢
Jar批量管理小工具
XML的解析
He worked as a foreign lead and paid off all the housing loans in a year
Robot reinforcement learning synergies between pushing and grassing with self supervised DRL (2018)
Some basic functions of enterprise projects are developed, and important things are saved to online first a
How many triangles are there in the golden K-line diagram?
Why does infographic help your SEO
How to effectively monitor the DC column head cabinet
Netcore3.1 JSON web token Middleware
Using fast parsing intranet penetration to realize zero cost self built website
随机推荐
It's too convenient. You can complete the code release and approval by nailing it!
Solve the problem that the virtual machine cannot be remotely connected through SSH service
【kotlin】第三天
45岁教授,她投出2个超级独角兽
Intelligence test to see idioms guess ancient poems wechat applet source code
Using the uniapp rich text editor
js如何实现数组转树
Expand your kubecl function
After Microsoft disables the IE browser, open the IE browser to flash back the solution
华泰证券低佣金的开户链接安全吗?
Acrel-EMS综合能效平台在校园建设的意义
Life is changeable, and the large intestine covers the small intestine. This time, I can really go home to see my daughter-in-law...
跨域请求
使用快解析搭建自己的minecraft服务器
「运维有小邓」域密码策略强化器
Parsing of XML
人生无常,大肠包小肠, 这次真的可以回家看媳妇去了。。。
挖财学院开户安全的吗?开户怎么开?
js正则表达式之中文验证(转)
Application of multi loop instrument in base station "switching to direct"