首页 > 其他分享 >SCC缩点

SCC缩点

时间：2024-05-08 16:57:46浏览次数：28  
标签：缩点 ch int MAX SCC dfn low 节点

一、P2812 校园网络【[USACO]Network of Schools加强版】

P2812 校园网络【[USACO]Network of Schools加强版】

1、算法简析

首先，建立一张有向图——学校是节点，学校间的单向线路是有向边。\(Q_1\)：选出若干个节点，从这些节点出发可以到达其它的任意节点（即不考虑选出的节点），求这些节点数量的最小值。\(Q_2\)：添加若干条有向边，使有向图中任意两点可以相互到达，求这些边数量的最小值。

我们知道，在强连通分量中，任意两点可以相互到达，所以对于一个强连通分量，只要有一个节点作为代表即可。因此，我们可以通过 \(Tarjan\) 算法求 \(SCC\)，用 \(SCC\) 的编号建立新的节点，代替相应的强连通分量。然后建立新图，对原图进行了简化。这就是 \(SCC\) 缩点问题。

接下来，在缩点后的新图（无环图 \(DAG\)）上讨论问题。

对于 \(Q_1\)，若一个节点的入度为 \(0\)，则其它节点不可能到达它，所以该点必须作为起点。因此，入度为 \(0\) 的节点个数即所求。

对于 \(Q_2\)，要使任意两点可以相互到达，那么任意节点的出入度都不能为 \(0\)。又要使添加的边数最少，可以令出度为 \(0\) 的节点指向入度为 \(0\) 的节点。若两种节点的数量相等，则该数即所求。若数量不等，则取二者的最大值。因此出入度为 \(0\) 的节点数的最大值即所求。

2、Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX = 1e4 + 3;
int N;
vector<int> G[MAX];
int dfn[MAX], low[MAX], tot;
stack<int> S;
bool instk[MAX];
int scc[MAX], cnt; 
int din[MAX], dout[MAX];      // din[x] -- 缩点i的入度; dout[x] -- 缩点i的出度

void tarjan(int u)
{
	dfn[u] = low[u] = ++tot;
	S.push(u), instk[u] = true;
	
	for (int i = 0; i < G[u].size(); ++i)
	{
		int v = G[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (instk[v])
			low[u] = min(low[u], dfn[v]);
	}
	
	if (dfn[u] == low[u])
	{
		int t;
		++cnt;
		do
		{
			t = S.top();
			S.pop(), instk[t] = false;
			scc[t] = cnt;
		} while (t != u);
	}
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
		int a;
		while (cin >> a && a)
			G[i].push_back(a);
	}
	
	// scc缩点处理 
	for (int i = 1; i <= N; ++i)
		if (!dfn[i])
			tarjan(i);
			
	// 计算出入度
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j < G[i].size(); ++j)
		{
			int v = G[i][j];
			if (scc[i] != scc[v])
			{
				++din[scc[v]];
				++dout[scc[i]];	
			}	
		}	
	}
	
	// 计算出入度为零的节点个数
	int a = 0, b = 0;
	for (int i = 1; i <= cnt; ++i)
	{
		if (!din[i])    ++a;
		if (!dout[i])    ++b;
	}
	
	// 问1：入度为0的节点即所求
	cout << a << endl;
	// 问2：要满足题意，则所有节点的出入度都不为0。
	// 要使使用的边最少，则将出度为0的节点指向入度为0的节点。
	// 两种节点的个数相等的情况下，两者的个数即所求。
	// 若不相等，取二者的max。
	if (cnt == 1)    cout << 0 << endl;    // 特判，此时原图就是连通的，不需要添边 
	else    cout << max(a, b) << endl; 
	
	return 0;
}

二、P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

1、算法简析

建立有向图模型：奶牛是节点，“喜欢”是有向边。因为强连通分量的定义，所以一个强连通分量中的奶牛都可能是“明星”。因此，我们进行 \(SCC\) 缩点处理，使原图变成 \(DAG\) 图。此时，若我们选择一个入度为 \(0\) 的节点作为根节点，向上拉直，就形成了一棵树（当然，原图可能是不连通的，所以也可能形成森林）。显然，树（森林）的叶子节点就是所求。换句话说，也就是出度为 \(0\) 的 \(SCC\) 中的节点即所求。

需要注意的是，若出度为 \(0\) 的 \(SCC\) 的个数大于 \(1\)，则满足条件的节点个数为 \(0\)。因为“明星奶牛”需要能被所有节点访问，若存在其它节点的出度为 \(0\)，显然就不能满足要求。也就是说，形成的树（森林）的叶子节点只能有一个。或者，出度为 \(0\) 的 \(SCC\) 的个数只能为 \(1\)。

2、Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll quickin(void)
{
	ll ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 1e4 + 3;
int N, M;
vector<int> G[MAX];
int dfn[MAX], low[MAX], tot;
stack<int> S;
bool instk[MAX];
int scc[MAX], siz[MAX], cnt;
int dout[MAX];

void tarjan(int u)
{
	dfn[u] = low[u] = ++tot;
	S.push(u), instk[u] = true;
	
	for (int i = 0; i < G[u].size(); ++i)
	{
		int v = G[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (instk[v])
			low[u] = min(low[u], dfn[v]);
	}
	
	if (dfn[u] == low[u])
	{
		int t;
		++cnt;
		do
		{
			t = S.top();
			S.pop(), instk[t] = false;
			scc[t] = cnt;
			++siz[cnt];
		} while (t != u);
	}
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	N = quickin(), M = quickin();
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		a = quickin(), b = quickin();
		G[a].push_back(b);
	}
	
	for (int i = 1; i <= N; ++i)
		if (!dfn[i])
			tarjan(i);
			
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j < G[i].size(); ++j)
		{
			int v = G[i][j];
			if (scc[i] != scc[v])
			{
				++dout[scc[i]];
			}
		}
	}
	
	int sum = 0, zeros = 0; // sum -- 出度为0的SCC包含的节点个数; zeors -- 出度为0的SCC个数
	for (int i = 1; i <= cnt; ++i)
	{
		if (!dout[i])
		{
			sum += siz[i];
			++zeros;
		}
	}
	
	if (zeros > 1)    sum = 0; // 特判：若存在两个及以上的SCC出度为0，它们肯定无法相互访问，都不满足要求 
	cout << sum << endl;
	
	return 0;
}

三、P3387 【模板】缩点

P3387 【模板】缩点

1、算法简析

对于本题，我们可以先进行缩点，建立一张新的 \(DAG\) 图，然后在新图上寻找最大的权值之和。

注意，\(SCC\) 缩点后，新节点的编号满足拓扑序列。因此，可以用动态规划求最大值。

2、Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll quickin(void)
{
	ll ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 1e4 + 3;
int N, M, worth[MAX];
vector<int> G[MAX];
int dfn[MAX], low[MAX], tot;
stack<int> S;
bool instk[MAX];
int scc[MAX], cnt;
int nworth[MAX];         // 新图中各节点的权值 
vector<int> nG[MAX];     // 新图中的边 
int dp[MAX];             // dp[u] -- 以u为起点的路径的最大值 

void tarjan(int u)
{
	dfn[u] = low[u] = ++tot;
	S.push(u), instk[u] = true;
	
	for (int i = 0; i < G[u].size(); ++i)
	{
		int v = G[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (instk[v])
			low[u] = min(low[u], dfn[v]);
	}
	
	if (dfn[u] == low[u])
	{
		int t;
		++cnt;
		do
		{
			t = S.top();
			S.pop(), instk[t] = false;
			scc[t] = cnt;
		} while (t != u);
	}
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	N = quickin(), M = quickin();
	for (int i = 1; i <= N; ++i)
		worth[i] = quickin();
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		a = quickin(), b = quickin();
		G[a].push_back(b);
	}
	
	for (int i = 1; i <= N; ++i)
		if (!dfn[i])
			tarjan(i);
			
	for (int u = 1; u <= N; ++u)
	{
		nworth[scc[u]] += worth[u];              // 新节点的权值 
		for (int i = 0; i < G[u].size(); ++i)
		{
			int v = G[u][i];
			if (scc[u] != scc[v])                // 存新边 
				nG[scc[u]].push_back(scc[v]);
		}
	}
	
	// SCC缩点后的新节点的编号按降序满足拓扑序列
	for (int u = 1; u <= N; ++u)
	{
		if (dp[u] == 0)    dp[u] = nworth[u];

		for (int i = 0; i < nG[u].size(); ++i)
		{
			int v = nG[u][i];
			dp[u] = max(dp[u], dp[v] + nworth[u]);
		}
	}
	
	int ans = 0;
	for (int i = 1; i <= cnt; ++i)
		ans = max(ans, dp[i]);
		
	cout << ans << endl; 
	
	return 0;
}

完

标签：缩点,ch,int,MAX,SCC,dfn,low,节点
From： https://www.cnblogs.com/hoyd/p/18180213

相关文章

  • ISCC线上赛2023
    ISCC线上赛2023webweb1双重base解码得到flagweb3F12控制台查看可找到loveStory.phpEnc.phpdownload.php，loveStory.php为反序列源码boy::__destruct()-->girl()::__call()-->helper()::__isset()-->boy()::__toString()-->helper()::__get()-->love_story()::__love()......
  • [CSCCTF 2019 Qual]FlaskLight
    [CSCCTF2019Qual]FlaskLight打开环境源代码里发现可通过GET方式传入参数简单验证发现存在SSTI{{''.__class__.__mro__[2].__subclasses__()}}#可以爆出所有的类编写脚本查找可利用的类利用subprocess.Popen执行命令importrequestsimportreimporthtmlimportt......
  • SAP S4HANA 2023 PCE系统上的SCC1？
    SAPS4HANA2023PCE系统上的SCC1？  在S/4HANA2023PCE系统上执行事务代码SCC1,    系统提示：”传输工具的旧副本已弃用，新的传输复制工具可用，是否继续执行新事务代码SCC1N?”. 点击按钮’是’,系统进入如下界面：    输入TR号码，输入源客户端，   ......
  • 强连通分量、缩点
    强连通分量定义：强连通分量是指一个任意两点都可互相到达的极大子图。求解思路和桥、割点和边双连通分量很类似。首先跑出一颗dfs树，令\(dfn_u\)表示\(u\)的时间戳，\(low_u\)表示\(u\)的子树中仅通过非树边能到达的\(\min\{dfn_v\}\)。比如下图：在这张图中，黑色边为树边......
  • SCC学习笔记
    SCC学习笔记好听点的话来说，就是强连通分量。一个有向图，里面任意两个节点之间可以相互到达，我们把它称为一个强连通分量。Kosaraju首先，对于一个强连通的图，显然，他的反图也是一个强连通图。（因为原先\(A\)可以到\(B\)，\(B\)可以到\(A\)，反过来是一样的）做法是从任意一个点开始，......
  • 同一SAP系统下使用SCC1跨客户端(client)传输配置
    abap开发中会涉及到一些配置的，也会生成定制请求，比如说BTE中的配置，webservice中的端口配置。这些配置并不是跨client的，通常一个SAP系统内会有多个client，比如，开发机系统内存在两个client，100和200，100下是纯开发client，200下会有一点简单测试数据，100，200之间的系统内配置传输就会用到SC......
  • How to survive in ISSCC -- 下
    上次讲了day.0到day.3的故事，现在继续更新哈哈。day.4这次ISSCC我们报了demosession，所以除了pre之外还得去演示demo，我们在demosession2，也就是pre的前一天进行演示。demosession的时间是下午5点到7点，主办方会提供一个展位和banner，展位上有桌子，展板，还有电源。作者需要自己准......
  • Tarjan算法求SCC，缩点
    Tanjan算法可以在O(n+m)的时间内求出强连通分量，常数小，是个非常优秀的算法。算法实现过程：dfn[x]表示x的dfs生成树上的编号，代表着时间戳，low[x]表示从x结点出发，能够访问到最早的时间戳。<1>进入u时，盖上时间戳，结点入栈。<2>枚举该点的结点的时候，分为三种情况：（1）如果该点v没有访......
  • 学习笔记——缩点
    前置知识：Tarjan求强连通分量一、什么是缩点缩点，就是把一张有向有环图上的一个个环缩成点，使其变成有向无环图。二、缩点的应用求最长路时常用。标准问法：给定一个有向图，每个点有一个权值，允许多次经过一条边或者一个点，重复经过的点，权值只计算一次。求最大权值若直接......
  • 强连通分量（SCC，Strongly Connected Components）学习笔记 & edited in 2024.01.31
    更新日志upd2024.01.31写好文章基本内容upd2024.01.31发表于洛谷upd2024.02.01同步发表于CSDNupd2024.02.01同步发表于博客园cnblogs强连通分量（SCC，StronglyConnectedComponents）定义强连通有向图（DAG）中若其中两点$x$，$y$能彼此到达（不一定是直接连边），称$x$和......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99