Dynamic Graph

118 阅读 0 评论 78 点赞

我是靠谱客的博主义气店员，最近开发中收集的这篇文章主要介绍Dynamic Graph，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：Dynamic Graph

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

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

AC代码：

#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;
}