OI 常用的模版代码

OI 常用的模版代码

2019年11月5日 2 作者 Null NaN

由nullnan友情整理,并同步发布于nullnan的博客

找环

使用拓扑排序

代码

<pre class="wp-block-syntaxhighlighter-code">int n,in[MAXN],to[MAXN];
std::queue<int> q;
bool vis[MAXN];
void toposort() {
	while(!q.empty()) {
		int now = q.front();q.pop();
		vis[now] = true;
		in[to[now]]--;
		if(!in[to[now]]) q.push(to[now]);
	}
}
int dfs(int now,int step) {
	if(vis[now]) {
		return step;
	}
	vis[now] = true;
	return dfs(to[now],step+1);
}
void solve() {
	foreach(i,1,n) {
		if(!in[i]) {
			q.push(i);
			vis[i] = true;
		}
	}
	toposort();
	int ans = INT_MAX;
	foreach(i,1,n) {
		if(!vis[i]) ans = std::min(ans,dfs(i,0));
	}
	printf("%d\n",ans);
}
int main() {
	read(n);
	foreach(i,1,n) {
		int x;
		read(x);
		to[i] = x;
		in[x]++;
	}
	solve();
	return 0;
}
// P2661题目要求求出最小环大小</pre>

在拓扑之后剩下的点一定在环上(但不一定只在一个环上)。

求割点

<pre class="wp-block-syntaxhighlighter-code">int n,m;
int dfn[MAXN],low[MAXN],dfs_cnt;
bool cut[MAXN];
void tarjan(int rt,int fa) {
	dfn[rt] = low[rt] = ++dfs_cnt;
	int child = 0;
	for(auto to : G[rt]) {
		if(!dfn[to]) {
			tarjan(to,fa);
			low[rt] = std::min(low[rt],low[to]);
			if(low[to] >= dfn[rt] && rt != fa) cut[rt] = true;
			if(rt == fa) child++; 
		}
		low[rt] = std::min(low[rt],dfn[to]);
	}
	if(child >= 2 && rt == fa) cut[rt] = true;
}
void solve() {
	foreach(i,1,n) {
		if(!dfn[i]) tarjan(i,i);
	}
	int ans = 0;
	foreach(i,1,n) {
		if(cut[i]) ++ans;
	}
	cout << ans << '\n';
	foreach(i,1,n) {
		if(cut[i]) {
			cout << i << ' ';
		}
	} 
}</pre>

和tarjan求scc只差了一个栈和条件

二分图判定(不是匹配!!)使用bfs进行

在二分图G中,任选一个点V, 使用BFS算出其他点相对于V的距离(边权为1) 对于每一条边E,枚举它的两个端点,若其两个端点的值, 一个为奇数,一个为偶数,则图G为一个二分图。

<pre class="wp-block-syntaxhighlighter-code">const int MAXN = 200 + 5;
vector<int> G[MAXN];
vector<std::pair<int,int> > E;
int n,m;
int dist[MAXN];
bool vis[MAXN];
void bfs(int s) {
	std::queue<int> q;
	q.push(s);
	while(!q.empty()) {
		int now = q.front();q.pop();
		if(vis[now]) continue;
		vis[now] = true;
		for(auto to : G[now]) {
			dist[to] = dist[now] + 1;
		} 
	}
}
bool solve() {
	bfs(0);
	for(auto e : E) {
		if(dist[e.first] % 2 == 0 && dist[e.second] % 2 == 0) return false;
		if(dist[e.first] % 2 != 0 && dist[e.second] % 2 != 0) return false;
	}
	return true;
}
int main() {
	read(n,m);
	foreach(i,1,m) {
		int u,v;
		read(u,v);
		G[u].pb(v);
		G[v].pb(u);
		E.pb(std::make_pair(u,v));
	}
	puts(solve() ? "BICOLORABLE" : "NOT BICOLORABLE");
	return 0;
}

</pre>