题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
typedef pair<int,int> PII;
class Solution {
public:
vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
unordered_map<int,vector<PII>> g;
for(auto e:edges){
int a=e[0],b=e[1];
g[a].push_back({b,0});
g[b].push_back({a,1});
}
int res=0;
vector<int> ans(n);
function<void(int,int)> dfs1=[&](int u,int fa)
{
for(auto [v,w]:g[u])
{
if(v==fa) continue;
res+=w;
dfs1(v,u);
}
};
function<void(int,int,int)> dfs2=[&](int u,int fa,int s)
{
ans[u]=s;
for(auto [v,w]:g[u])
{
if(v==fa) continue;
if(w==1)
dfs2(v,u,s-1);
else dfs2(v,u,s+1);
}
};
dfs1(0,-1);
dfs2(0,-1,res);
return ans;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla