【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对
作者保举视频算法专题
本文涉及知识点
树上倍增 树 图论 并集查找 换根法 深度优先
割点原理及封装好的割点类(预计2024年3月11号左右发布）
LeetCode3067. 在带权树网络中统计可连接服务器对数量
给你一棵无根带权树，树中总共有 n 个节点，分别表现 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges = 表现节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。
如果两个服务器 a ，b 和 c 满意以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ：
a < b ，a != c 且 b != c 。
从 c 到 a 的距离是可以被 signalSpeed 整除的。
从 c 到 b 的距离是可以被 signalSpeed 整除的。
从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。
请你返回一个长度为 n 的整数数组 count ，其中 count 表现通过服务器 i 可连接 的服务器对的 数量 。
示例 1：
https://img-blog.csdnimg.cn/direct/23e598f996a84ff2924ab89729c5f129.png#pic_center
输入：edges = [,,,,], signalSpeed = 1
输出：
表明：由于 signalSpeed 等于 1 ，count 等于所有从 c 开始且没有公共边的路径对数量。
在输入图中，count 等于服务器 c 左边服务器数量乘以右边服务器数量。
示例 2：
https://img-blog.csdnimg.cn/direct/ffe7505a5bea485a9d4a1295ea391c78.png#pic_center
输入：edges = [,,,,,], signalSpeed = 3
输出：
表明：通过服务器 0 ，有 2 个可连接服务器对(4, 5) 和 (4, 6) 。
通过服务器 6 ，有 2 个可连接服务器对 (4, 5) 和 (0, 5) 。
所有服务器对都必须通过服务器 0 或 6 才可连接，所以其他服务器对应的可连接服务器对数量都为 0 。
提示：
2 <= n <= 1000
edges.length == n - 1
edges.length == 3
0 <= ai, bi < n
edges =
1 <= weighti <= 106
1 <= signalSpeed <= 106
输入保证 edges 构成一棵正当的树。
树上倍增
本题有三个考点：
一，怎样计算树上两个节点x1,x2的距离。
假定这两个节点的最早公共先人是pub。以恣意节点root为根，f(x)表现节点x到root的距离。
x1到x2的距离：f(x1)+f(x2)-2*f(pub)。
二，怎样找到最早公共先人：树上倍增。
记录各节点的1级先人（父节点）、2级先人、4级先人…
三，如果判定ac和bc有公共边。
树是连通无向无环图，因为无环，所以两个节点的路径唯一。
假设公共边是x3x4。则x3到c的路径唯一，假定x3到c的倒数第二个端点是x5，则ab和bc的末了一条边都是 x 3 c → \overrightarrow{x3c} x3c 。断开所以和c相连的边，如果a和b在同一个连通区域，则有公共边。用并查集看是否在同一个连通区域。
时间复杂度： O(nnlogn)。 枚举c，时间复杂度O(n)；枚举ab，时间复杂度O(n)。查公共路径O(logn)。
并集查找
class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>>vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
}
}
return vNeiBo;
}
};
class CUnionFind
{
public:
CUnionFind(int iSize) :m_vNodeToRegion(iSize)
{
for (int i = 0; i < iSize; i++)
{
m_vNodeToRegion = i;
}
m_iConnetRegionCount = iSize;
}
CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
{
for (int i = 0; i < vNeiBo.size(); i++) {
for (const auto& n : vNeiBo) {
Union(i, n);
}
}
}
int GetConnectRegionIndex(int iNode)
{
int& iConnectNO = m_vNodeToRegion;
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectRegionIndex(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectRegionIndex(iNode1);
const int iConnectNO2 = GetConnectRegionIndex(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return;
}
m_iConnetRegionCount--;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
return m_iConnetRegionCount;
}
vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
{
const int iNodeSize = m_vNodeToRegion.size();
vector<int> vRet(iNodeSize);
for (int i = 0; i < iNodeSize; i++)
{
vRet++;
}
return vRet;
}
std::unordered_map<int, vector<int>> GetNodeOfRegion()
{
std::unordered_map<int, vector<int>> ret;
const int iNodeSize = m_vNodeToRegion.size();
for (int i = 0; i < iNodeSize; i++)
{
ret.emplace_back(i);
}
return ret;
}
private:
void UnionConnect(int iFrom, int iTo)
{
m_vNodeToRegion = iTo;
}
vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
int m_iConnetRegionCount;
};
class CParents
{
public:
CParents(vector<int>& vParent, const vector<int>& vLeve):m_vLeve(vLeve)
{
const int iMaxLeve = *std::max_element(vLeve.begin(), vLeve.end());
int iBitNum = 0;
for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
const int n = vParent.size();
m_vParents.assign(iBitNum+1, vector<int>(n, -1));
m_vParents = vParent;
//树上倍增
for (int i = 1; i < m_vParents.size(); i++)
{
for (int j = 0; j < n; j++)
{
const int iPre = m_vParents;
if (-1 != iPre)
{
m_vParents = m_vParents;
}
}
}
}
int GetParent(int iNode, int iLeve)const
{
int iParent = iNode;
for (int iBit = 0; iBit < m_vParents.size(); iBit++)
{
if (-1 == iParent)
{
return iParent;
}
if (iLeve & (1 << iBit))
{
iParent = m_vParents;
}
}
return iParent;
}
int GetPublicParent(int iNode1, int iNode2)const
{
int leve0 = m_vLeve;
int leve1 = m_vLeve;
if (leve0 < leve1)
{
iNode2 = GetParent(iNode2, leve1 - leve0);
leve1 = leve0;
}
else
{
iNode1 = GetParent(iNode1, leve0 - leve1);
leve0 = leve1;
}
//二分查找
int left = -1, r = leve0;
while (r - left > 1)
{
const auto mid = left + (r - left) / 2;
const int iParent0 = GetParent(iNode1, mid);
const int iParent1 = GetParent(iNode2, mid);
if (iParent0 == iParent1)
{
r = mid;
}
else
{
left = mid;
}
}
return GetParent(iNode1, r);
}
protected:
vector<vector<int>> m_vParents;
const vector<int> m_vLeve;
};
class Solution {
public:
vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
m_c = edges.size() + 1;
m_vDisToRoot.resize(m_c);
m_vParent.resize(m_c);
m_vLeve.resize(m_c);
auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
DFS(neiBo, 0, -1, 0,0);
CParents par(m_vParent,m_vLeve);
vector<int> vRet(m_c);
for (int c = 0; c < m_c; c++)
{
CUnionFind uf(m_c);
for (const auto& v : edges)
{
if ((v == c) || (v == c))
{
continue;
}
uf.Union(v, v);
}
vector<int> vRegionCnt(m_c);
for (int ab = 0; ab < m_c; ab++)
{
if (ab == c )
{
continue;
}
const int pub = par.GetPublicParent(ab, c);
const int len = m_vDisToRoot + m_vDisToRoot - 2 * m_vDisToRoot;
if (0 != len % signalSpeed)
{
continue;
}
vRegionCnt++;
}
int&iRet = vRet;
const int total = std::accumulate(vRegionCnt.begin(), vRegionCnt.end(), 0);
for (int c1 = 0; c1 < m_c; c1++)
{
iRet += vRegionCnt * (total - vRegionCnt);
}
iRet /= 2;
}
return vRet;
}
void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int leve,int dis)
{
m_vDisToRoot =dis;
m_vParent = par;
m_vLeve = leve;
for (const auto& : neiBo)
{
if (next == par)
{
continue;
}
DFS(neiBo, next, cur,leve+1,dis+len);
}
}
vector<int> m_vDisToRoot,m_vParent,m_vLeve;
int m_c;
};
测试用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1, v2);
}
}
int main()
{
vector<vector<int>> edges;
int signalSpeed;
{
Solution sln;
edges = {}, signalSpeed = 1;
auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
Assert({ 0 }, res);
}
{
Solution sln;
edges = { {0,1,1} }, signalSpeed = 1;
auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
Assert({ 0,0 }, res);
}
{
Solution sln;
edges = { {0,1,1},{1,2,1} }, signalSpeed = 1;
auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
Assert({ 0,1,0 }, res);
}
{
Solution sln;
edges = { {0,1,1},{1,2,5},{2,3,13},{3,4,9},{4,5,2} }, signalSpeed = 1;
auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
Assert({ 0,4,6,6,4,0 } , res);
}
{
Solution sln;
edges = { {0,6,3},{6,5,3},{0,3,1},{3,2,7},{3,1,6},{3,4,2} }, signalSpeed = 3;
auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
Assert({ 2,0,0,0,0,0,2 }, res);
}
}
换根法DFS
树中删除一个节点，则各孩子各一个连通区域，除本身及子女外一个区域。如果这个节点是根，则简朴得多。各孩子一个连通区域。
DSF(cur) 返回本身及子孙到当前根节点距离是signalSpeed 倍的节点数量。令当前根节点各孩子的返回值是{i1,i2, ⋯ \cdots ⋯,im} 。i1*i2+(i1+i2)*i3 ⋯ \cdots ⋯ +(I1+i2+ … \dots … + i m − 1 _{m-1} m−1)*im。如许不必除以二。
a<b ，表现a !=b ，(a,b)和(b,a)只取一个。
class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>>vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
}
}
return vNeiBo;
}
};
class Solution {
public:
vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
m_c = edges.size() + 1;
m_iSignalSpeed = signalSpeed;
auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
vector<int> vRet(m_c);
for (int c = 0; c < m_c; c++)
{
int& iRet = vRet;
int left = 0;
for (const auto& : neiBo)
{
int cur = DFS(neiBo, next, c, len);
iRet += left * cur;
left += cur;
}
}
return vRet;
}
int DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par,int dis)
{
int iRet = (0 ==dis % m_iSignalSpeed);
for (const auto& : neiBo)
{
if (next == par)
{
continue;
}
iRet +=DFS(neiBo, next, cur,dis+len);
}
return iRet;
}
int m_iSignalSpeed;
int m_c;
};
割点
本解法过于复杂，除非用了提前封装好的割点扩展类，否则被使用。
class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>>vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
}
}
return vNeiBo;
}
};
class CUnionFind
{
public:
CUnionFind(int iSize) :m_vNodeToRegion(iSize)
{
for (int i = 0; i < iSize; i++)
{
m_vNodeToRegion = i;
}
m_iConnetRegionCount = iSize;
}
CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
{
for (int i = 0; i < vNeiBo.size(); i++) {
for (const auto& n : vNeiBo) {
Union(i, n);
}
}
}
int GetConnectRegionIndex(int iNode)
{
int& iConnectNO = m_vNodeToRegion;
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectRegionIndex(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectRegionIndex(iNode1);
const int iConnectNO2 = GetConnectRegionIndex(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return;
}
m_iConnetRegionCount--;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
return m_iConnetRegionCount;
}
vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
{
const int iNodeSize = m_vNodeToRegion.size();
vector<int> vRet(iNodeSize);
for (int i = 0; i < iNodeSize; i++)
{
vRet++;
}
return vRet;
}
std::unordered_map<int, vector<int>> GetNodeOfRegion()
{
std::unordered_map<int, vector<int>> ret;
const int iNodeSize = m_vNodeToRegion.size();
for (int i = 0; i < iNodeSize; i++)
{
ret.emplace_back(i);
}
return ret;
}
private:
void UnionConnect(int iFrom, int iTo)
{
m_vNodeToRegion = iTo;
}
vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
int m_iConnetRegionCount;
};
class CParents
{
public:
CParents(vector<int>& vParent, const int iMaxLeve)
{
int iBitNum = 0;
for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
const int n = vParent.size();
m_vParents.assign(iBitNum+1, vector<int>(n, -1));
m_vParents = vParent;
//树上倍增
for (int i = 1; i < m_vParents.size(); i++)
{
for (int j = 0; j < n; j++)
{
const int iPre = m_vParents;
if (-1 != iPre)
{
m_vParents = m_vParents;
}
}
}
}
int GetParent(int iNode, int iLeve)const
{
int iParent = iNode;
for (int iBit = 0; iBit < m_vParents.size(); iBit++)
{
if (-1 == iParent)
{
return iParent;
}
if (iLeve & (1 << iBit))
{
iParent = m_vParents;
}
}
return iParent;
}
protected:
vector<vector<int>> m_vParents;
};
class C2Parents : CParents
{
public:
C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve)
, CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end()))
{
}
int GetPublicParent(int iNode1, int iNode2)const
{
int leve0 = m_vLeve;
int leve1 = m_vLeve;
if (leve0 < leve1)
{
iNode2 = GetParent(iNode2, leve1 - leve0);
leve1 = leve0;
}
else
{
iNode1 = GetParent(iNode1, leve0 - leve1);
leve0 = leve1;
}
//二分查找
int left = -1, r = leve0;
while (r - left > 1)
{
const auto mid = left + (r - left) / 2;
const int iParent0 = GetParent(iNode1, mid);
const int iParent1 = GetParent(iNode2, mid);
if (iParent0 == iParent1)
{
r = mid;
}
else
{
left = mid;
}
}
return GetParent(iNode1, r);
}
protected:
vector<vector<int>> m_vParents;
const vector<int> m_vLeve;
};
class CCutPointEx
{
public:
CCutPointEx(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
{
m_vNodeToTime.assign(m_iSize, -1);
m_vChildFirstEnd.resize(m_iSize);
m_vNodeToRegion.assign(m_iSize, -1);
m_vCut.assign(m_iSize, false);
for (int i = 0; i < m_iSize; i++)
{
if (-1 != m_vNodeToTime)
{
continue;
}
dfs(i, -1, vNeiB);
m_iRegionCount++;
}
m_vTimeToNode.resize(m_iSize);
for (int i = 0; i < m_iSize; i++)
{
m_vTimeToNode] = i;;
}
}
bool Visit(int src, int dest, int iCut)const
{
if (m_vNodeToRegion != m_vNodeToRegion)
{
return false;//不在一个连通区域
}
if (!m_vCut)
{
return true;
}
const int r1 = GetCutRegion(iCut, src);
const int r2 = GetCutRegion(iCut, dest);
return r1 == r2;
}
vector<vector<int>> GetSubRegionOfCut(const int iCut)const
{//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点一个区域
//父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的区域。
const auto& v = m_vChildFirstEnd;
vector<vector<int>> vRet(1);
int j = 0;
for (int iTime=0;iTime < m_iSize; iTime++ )
{
const int iNode = m_vTimeToNode;
if ((j < v.size()) && ( iTime>= v.first ))
{
j++;
vRet.emplace_back();
}
if ((iCut != iNode) && (m_vNodeToRegion == m_vNodeToRegion))
{
if (v.size()&&(iTime >= v.back().second))
{
vRet.emplace_back(iNode);
}
else
{
vRet.back().emplace_back(iNode);
}
}
}
return vRet;
}
protected:
int dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
{
auto& curTime = m_vNodeToTime;
m_vNodeToRegion = m_iRegionCount;
curTime = m_iTime++;
int iCutChild = 0;
int iMinTime = curTime;
for (const auto& next : vNeiB)
{
if (-1 != m_vNodeToTime)
{
iMinTime = min(iMinTime, m_vNodeToTime);
continue;
}
int iChildBeginTime = m_iTime;
const int iChildMinTime = dfs(next, cur, vNeiB);
iMinTime = min(iMinTime, iChildMinTime);
if (iChildMinTime >= curTime)
{
iCutChild++;
m_vChildFirstEnd.push_back({ iChildBeginTime,m_iTime });
};
}
m_vCut = (iCutChild + (-1 != parent)) >= 2;
return iMinTime;
}
int GetCutRegion(int iCut, int iNode)const
{
const auto& v = m_vChildFirstEnd;
auto it = std::upper_bound(v.begin(), v.end(), m_vNodeToTime, [](int time, const std::pair<int, int>& pr) {return time < pr.first; });
if (v.begin() == it)
{
return v.size();
}
--it;
return (it->second > m_vNodeToTime) ? (it - v.begin()) : v.size();
}
int m_iTime = 0;
const int m_iSize;//时间戳
int m_iRegionCount = 0;
vector<int> m_vNodeToTime;//各节点到达时间，从0开始。 -1表示未处理
vector<bool> m_vCut;//是否是割点
vector<int> m_vNodeToRegion;//各节点所在区域
vector<vector<pair<int, int>>> m_vChildFirstEnd;//左闭右开空间.first)和[m_vChildFirstEnd.back().second,iSize)是一个区域
vector<int> m_vTimeToNode;
};
2024年3月9号 新封装
class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>>vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
if (!bDirect)
{
vNeiBo - iBase].emplace_back(v - iBase, v);
}
}
return vNeiBo;
}
};
class CUnionFind
{
public:
CUnionFind(int iSize) :m_vNodeToRegion(iSize)
{
for (int i = 0; i < iSize; i++)
{
m_vNodeToRegion = i;
}
m_iConnetRegionCount = iSize;
}
CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
{
for (int i = 0; i < vNeiBo.size(); i++) {
for (const auto& n : vNeiBo) {
Union(i, n);
}
}
}
int GetConnectRegionIndex(int iNode)
{
int& iConnectNO = m_vNodeToRegion;
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectRegionIndex(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectRegionIndex(iNode1);
const int iConnectNO2 = GetConnectRegionIndex(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return;
}
m_iConnetRegionCount--;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
return m_iConnetRegionCount;
}
vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
{
const int iNodeSize = m_vNodeToRegion.size();
vector<int> vRet(iNodeSize);
for (int i = 0; i < iNodeSize; i++)
{
vRet++;
}
return vRet;
}
std::unordered_map<int, vector<int>> GetNodeOfRegion()
{
std::unordered_map<int, vector<int>> ret;
const int iNodeSize = m_vNodeToRegion.size();
for (int i = 0; i < iNodeSize; i++)
{
ret.emplace_back(i);
}
return ret;
}
private:
void UnionConnect(int iFrom, int iTo)
{
m_vNodeToRegion = iTo;
}
vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
int m_iConnetRegionCount;
};
class CParents
{
public:
CParents(vector<int>& vParent, const int iMaxLeve)
{
int iBitNum = 0;
for (; (1 << iBitNum) < iMaxLeve; iBitNum++);
const int n = vParent.size();
m_vParents.assign(iBitNum+1, vector<int>(n, -1));
m_vParents = vParent;
//树上倍增
for (int i = 1; i < m_vParents.size(); i++)
{
for (int j = 0; j < n; j++)
{
const int iPre = m_vParents;
if (-1 != iPre)
{
m_vParents = m_vParents;
}
}
}
}
int GetParent(int iNode, int iLeve)const
{
int iParent = iNode;
for (int iBit = 0; iBit < m_vParents.size(); iBit++)
{
if (-1 == iParent)
{
return iParent;
}
if (iLeve & (1 << iBit))
{
iParent = m_vParents;
}
}
return iParent;
}
protected:
vector<vector<int>> m_vParents;
};
class C2Parents : CParents
{
public:
C2Parents(vector<int>& vParent, const vector<int>& vLeve) :m_vLeve(vLeve)
, CParents(vParent,*std::max_element(vLeve.begin(), vLeve.end()))
{
}
int GetPublicParent(int iNode1, int iNode2)const
{
int leve0 = m_vLeve;
int leve1 = m_vLeve;
if (leve0 < leve1)
{
iNode2 = GetParent(iNode2, leve1 - leve0);
leve1 = leve0;
}
else
{
iNode1 = GetParent(iNode1, leve0 - leve1);
leve0 = leve1;
}
//二分查找
int left = -1, r = leve0;
while (r - left > 1)
{
const auto mid = left + (r - left) / 2;
const int iParent0 = GetParent(iNode1, mid);
const int iParent1 = GetParent(iNode2, mid);
if (iParent0 == iParent1)
{
r = mid;
}
else
{
left = mid;
}
}
return GetParent(iNode1, r);
}
protected:
vector<vector<int>> m_vParents;
const vector<int> m_vLeve;
};
//割点
class CCutPoint
{
public:
CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
{
m_vNodeToTime.assign(m_iSize, -1);
m_vCutNewRegion.resize(m_iSize);
for (int i = 0; i < m_iSize; i++)
{
if (-1 == m_vNodeToTime)
{
m_vRegionFirstTime.emplace_back(m_iTime);
dfs(vNeiB, i, -1);
}
}
}
int dfs(const vector<vector<int>>& vNeiB,const int cur, const int parent)
{
int iMinTime = m_vNodeToTime = m_iTime++;
int iRegionCount = (-1 != parent);//根连通区域数量
for (const auto& next : vNeiB) {
if (-1!= m_vNodeToTime) {
iMinTime = min(iMinTime, m_vNodeToTime);
continue;
}
const int childMinTime = dfs(vNeiB, next, cur);
iMinTime = min(iMinTime, childMinTime);
if (childMinTime >= m_vNodeToTime) {
iRegionCount++;
m_vCutNewRegion.emplace_back(m_vNodeToTime, m_iTime);
}
}
if (iRegionCount < 2)
{
m_vCutNewRegion.clear();
}
return iMinTime;
}
const int m_iSize;
const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳
const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳
vector<bool> Cut()const {
vector<bool> ret;
for (int i = 0; i < m_iSize; i++)
{
ret.emplace_back(m_vCutNewRegion.size());
}
return ret; }//
const vector < vector<pair<int, int>>>& NewRegion()const { return m_vCutNewRegion; };
protected:
vector<int> m_vNodeToTime;
vector<int> m_vRegionFirstTime;
vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion如果存在[left,r) 表示割掉c后，时间戳[left,r)的节点会形成新区域
int m_iTime = 0;
};
class CConnectAfterCutPoint
{
public:
CConnectAfterCutPoint(const vector<vector<int>>& vNeiB) :m_ct(vNeiB)
{
m_vTimeToNode.resize(m_ct.m_iSize);
m_vNodeToRegion.resize(m_ct.m_iSize);
for (int iNode = 0; iNode < m_ct.m_iSize; iNode++)
{
m_vTimeToNode] = iNode;
}
for (int iTime = 0,iRegion= 0; iTime < m_ct.m_iSize; iTime++)
{
if ((iRegion < m_ct.RegionFirstTime().size()) && (m_ct.RegionFirstTime() == iTime))
{
iRegion++;
}
m_vNodeToRegion] = (iRegion - 1);
}
}
bool Connect(int src, int dest, int iCut)const
{
if (m_vNodeToRegion != m_vNodeToRegion)
{
return false;//不在一个连通区域
}
if (0 == m_ct.NewRegion().size())
{//不是割点
return true;
}
const int r1 = GetCutRegion(iCut, src);
const int r2 = GetCutRegion(iCut, dest);
return r1 == r2;
}
vector<vector<int>> GetSubRegionOfCut(const int iCut)const
{//删除iCut及和它相连的边后，iCut所在的区域会分成几个区域：父节点一个区域、各子节点 一个区域
//父节点所在区域可能为空，如果iCut所在的连通区域只有一个节点，则返回一个没有节点的 区域。
const auto& v = m_ct.NewRegion();
vector<int> vParen;
const int iRegion = m_vNodeToRegion;
const int iEndTime = (iRegion + 1 == m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime();
vector<vector<int>> vRet;
for (int iTime = m_ct.RegionFirstTime(),j=-1; iTime < iEndTime; iTime++)
{
if (iCut == m_vTimeToNode)
{
continue;
}
if ((j + 1 < v.size()) && (v.first == iTime))
{
j++;
vRet.emplace_back();
}
const int iNode = m_vTimeToNode;
if ((-1 != j ) && (iTime >= v.first) && (iTime < v.second))
{
vRet.back().emplace_back(iNode);
}
else
{
vParen.emplace_back(iNode);
}
}
vRet.emplace_back();
vRet.back().swap(vParen);
return vRet;
}
protected:
int GetCutRegion(int iCut, int iNode)const
{
const auto& v = m_ct.NewRegion();
auto it = std::upper_bound(v.begin(), v.end(), m_ct.Time(), [](int time, const std::pair<int, int>& pr) {returntime < pr.first; });
if (v.begin() == it)
{
return v.size();
}
--it;
return (it->second > m_ct.Time()) ? (it - v.begin()) : v.size();
}
vector<int> m_vTimeToNode;
vector<int> m_vNodeToRegion;//各节点所在区域
const CCutPoint m_ct;
};
class Solution {
public:
vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
m_c = edges.size() + 1;
m_vDisToRoot.resize(m_c);
m_vParent.resize(m_c);
m_vLeve.resize(m_c);
auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
DFS(neiBo, 0, -1, 0, 0);
C2Parents par(m_vParent, m_vLeve);
auto neiBo2 = CNeiBo::Two(m_c, edges, false, 0);
CConnectAfterCutPoint cut(neiBo2);
vector<int> vRet(m_c);
for (int c = 0; c < m_c; c++)
{
auto regs = cut.GetSubRegionOfCut(c);
int left = 0;
int& iRet = vRet;
for (const auto& subRegion : regs)
{
int cur = 0;
for (const auto& ab : subRegion)
{
const int pub = par.GetPublicParent(ab, c);
const int len = m_vDisToRoot + m_vDisToRoot - 2 * m_vDisToRoot;
if (0 != len % signalSpeed)
{
continue;
}
cur++;
}
iRet += left * cur;
left += cur;
}
}
return vRet;
}
void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par, int leve, int dis)
{
m_vDisToRoot = dis;
m_vParent = par;
m_vLeve = leve;
for (const auto& : neiBo)
{
if (next == par)
{
continue;
}
DFS(neiBo, next, cur, leve + 1, dis + len);
}
}
vector<int> m_vDisToRoot, m_vParent, m_vLeve;
int m_c;
};
DFS取代树上倍增
时间复杂度的瓶颈在 树上倍增。可以直接DFS 最近公共先人。
https://img-blog.csdnimg.cn/8d37dcd13ddb4df9af8f95fefd86828d.gif#pic_center#pic_center
扩展阅读
视频课程
有效学习：明确的目的 及时的反馈 拉伸区（难度符合），可以先学简朴的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的解说。
https://edu.csdn.net/course/detail/38771
怎样你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相干
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙，那算法就是他的是睛 测试环境
利用体系：win7 开发环境： VS2019 C++17
大概 利用体系：win10 开发环境： VS2022 **C+
+17**
如无特殊说明，本算法用**C++**实现。
https://img-blog.csdnimg.cn/f95ddae62a4e43a68295601c723f92fb.gif#pic_center
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]