CF505D Mr. Kitayuta's Technology 并查集拓扑排序

2021-03-21 15:25

阅读：674

标签：include mes printf ons http class 需要 space namespace

题意：

题面

分析：

~~在上届银牌学姐的帮助下~~

我们发现对于一个连通块若 \(m\) 个约束条件里共有 \(n\) 个点，那么答案一定是 \(n\) 或者 \(n-1\)

因为最多 \(n\) 条有向边可以将一个连通块变成一个强连通分量，而至少 \(n-1\) 条边才能保证 \(n\) 个点是联通的，所以对于每一个连通块我们只需要判断它是否存在一个环就可以了，有环的连通块答案就是 \(n\) ,没有的答案就是 \(n-1\) ,拓扑排序，\(tarjan\) ,暴搜都可以判环

代码：

#include

using namespace std;

namespace zzc
{
	int read(){
		int x=0,f=1;char ch=getchar();
		while(!isdigit(ch)){
			if(ch==‘-‘) f=-1;ch=getchar();
		}
		while(isdigit(ch)){
			x=(x q;
	struct edge
	{
		int to,nxt;
	}e[maxn];
	
	int find(int x)
	{
		return fa[x]==x?x:fa[x]=find(fa[x]);
	}
	
	void add(int u,int v)
	{
		e[++cnt].to=v;
		e[cnt].nxt=head[u];
		head[u]=cnt;
		rd[v]++;
	}
	
	void work()
	{
		int a,b;
		n=read();m=read();
		for(int i=1;i

CF505D Mr. Kitayuta's Technology 并查集拓扑排序

标签：include mes printf ons http class 需要 space namespace

原文地址：https://www.cnblogs.com/youth518/p/13904605.html

上一篇：2.编程语言介绍及Python解释器安装

下一篇：Java 8中处理集合的优雅姿势——Stream

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：CF505D Mr. Kitayuta's Technology 并查集拓扑排序
文章链接：http://soscw.com/index.php/essay/67225.html

亲，登录后才可以留言！

CF505D Mr. Kitayuta's Technology 并查集拓扑排序

题意：

分析：

代码：

评论

热门文章

推荐文章

最新文章

置顶文章

CF505D Mr. Kitayuta&#39;s Technology 并查集 拓扑排序

题意：

分析：

代码：

评论

热门文章

推荐文章

最新文章

置顶文章

CF505D Mr. Kitayuta's Technology 并查集拓扑排序