我是靠谱客的博主 义气店员,这篇文章主要介绍Dynamic Graph,现在分享给大家,希望可以做个参考。

题目链接:Dynamic Graph


很简单的一道题,但是要注意细节。

更新的时候暴力更新就好了,然后拓扑上面维护Bitset,但是要注意黑点不能直接跳过,直接不去更新颜色即可,如果直接跳过会导致某些点加不进来。


AC代码:

复制代码
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
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=310; int n,m,q,col[N],in[N],deg[N]; vector<int> g[N]; void Top(int now){ col[now]^=1; bitset<N> bt[N]; queue<int> q; for(int i=1;i<=n;i++) deg[i]=in[i]; for(int i=1;i<=n;i++) if(!deg[i]) q.push(i); for(int i=1;i<=n;i++) if(!col[i]) bt[i][i]=1; while(q.size()){ int u=q.front(); q.pop(); for(int to:g[u]){ if(!col[to]) bt[to]|=bt[u]; if(--deg[to]==0) q.push(to); } } int res=0; for(int i=1;i<=n;i++) if(!col[i]) res+=bt[i].count()-1; printf("%dn",res); } void solve(){ for(int i=1;i<=n;i++) g[i].clear(),in[i]=0,col[i]=0; for(int i=1,a,b;i<=m;i++) cin>>a>>b,g[a].push_back(b),in[b]++; for(int i=1,x;i<=q;i++) cin>>x,Top(x); } signed main(){ while(cin>>n>>m>>q) solve(); return 0; }

最后

以上就是义气店员最近收集整理的关于Dynamic Graph的全部内容,更多相关Dynamic内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(97)

评论列表共有 0 条评论

立即
投稿
返回
顶部