题目描述
n点n边肯定有环
所以先第一次拓扑找到环的点,第二次拓扑把在环的点标记一下答案在环里的点就是环大小
然后重新建边,环之间的边就别再连了,之后反向建边,拓扑排序叠加答案即可
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
vector<int> countVisitedNodes(vector<int>& edges) {
//n个点n条边 肯定有环
int n=edges.size();
vector<int> d(n);
unordered_map<int,vector<int>> g;
for(int i=0;i<edges.size();i++){
int a=i,b=edges[i];
g[a].push_back(b);
d[b]++;
}
queue<int> q;
vector<int> f(n);
for(int i=0;i<n;i++) if(d[i]==0) q.push(i);
while(q.size()){
auto t=q.front();
q.pop();
for(auto v:g[t]){
if(--d[v]==0){
q.push(v);
}
}
}
//把边已经全删了
for(int i=0;i<n;i++) if(d[i]) q.push(i);
vector<bool> st(n);
vector<int> res;
function<void(int)> dfs=[&](int u)
{
if(st[u]) return ;
st[u]=true;
res.push_back(u);
dfs(edges[u]);
};
unordered_set<int> s;
while(q.size())
{
auto t=q.front();
q.pop();
res.clear();
dfs(t);
int cnt=res.size();
for(auto v:res) f[v]+=cnt,s.insert(v);
}
g.clear();
fill(d.begin(),d.end(),0);
for(int i=0;i<edges.size();i++){
int a=i,b=edges[i];
if(s.count(a)&&s.count(b)) continue;
g[b].push_back(a);
d[a]++;
}
for(int i=0;i<n;i++) if(d[i]==0) q.push(i);
while(q.size()){
auto t=q.front();
q.pop();
for(auto v:g[t]){
f[v]=f[t]+1;
if(--d[v]==0){
q.push(v);
}
}
}
return f;
}
};
算法2
(暴力枚举) $O(n^2)$
直接缩点环再拓扑一次
时间复杂度
参考文献
C++ 代码
const int N=1e5+10,M=N;
class Solution {
public:
int h[N], e[M], ne[M], idx;
int dfn[N],low[N];
int scc_cnt,timestamp;
int stk[N],id[N];
bool in_stk[N];
int sz[N];
int top;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
low[u]=dfn[u]=++timestamp;
stk[++top]=u;
in_stk[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(in_stk[u])
low[u]=min(low[u],dfn[j]);
}
if(dfn[u]==low[u])
{
int y;
++scc_cnt;
do{
y=stk[top--];
in_stk[y]=false;
sz[scc_cnt]++;
id[y]=scc_cnt;
}while(y!=u);
}
}
vector<int> countVisitedNodes(vector<int>& edges) {
int n=edges.size();
scc_cnt=timestamp=top=0;
for(int i=0;i<=n;i++){
in_stk[i]=false;
dfn[i]=sz[i]=0;
h[i]=-1;
}
for(int i=0;i<edges.size();i++){
int a=i,b=edges[i];
add(a,b);
}
for(int i=0;i<n;i++)
if(dfn[i]==0) tarjan(i);
vector<int> f(n,1);
unordered_set<int> s;
for(int i=0;i<n;i++)
{
if(sz[id[i]]>1)
{
s.insert(i);
f[i]=sz[id[i]];
}
}
vector<int> d(n);
unordered_map<int,vector<int>> g;
for(int i=0;i<n;i++)
{
int a=i,b=edges[i];
if(s.count(a)&&s.count(b)) continue;
g[b].push_back(a);
d[a]++;
}
queue<int> q;
for(int i=0;i<n;i++) if(d[i]==0) q.push(i);
while(q.size()){
auto t=q.front();
q.pop();
for(auto v:g[t]){
f[v]+=f[t];
if(--d[v]==0) q.push(v);
}
}
return f;
}
};
常规基环树解法
const int N=1e5+10,INF=1e9;
class Solution {
public:
int h[N],ne[N],e[N],idx;
bool st[N],ins[N];
inline void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
vector<int> countVisitedNodes(vector<int>& edges) {
int n=edges.size();
idx=0;
vector<int> fu(n);
for(int i=0;i<=n;i++) h[i]=-1,st[i]=false,ins[i]=false;
for(int i=0;i<n;i++){
int a=i,b=edges[i];
add(a,b);
}
vector<int> f(n,1);
unordered_set<int> s;
std::function<void(int,int)> dfs_c=[&](int u,int from)
{
st[u] = ins[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
fu[j] = u;
if (!st[j]) dfs_c(j, i);
else if (ins[j])
{
int now=1;
for(int k=u;k!=j;k=fu[k]){
now++;
s.insert(k);
}
for(int k=u;k!=j;k=fu[k]) f[k]=now;
f[j]=now;
s.insert(j);
}
}
ins[u] = false;
};
for(int i=0;i<n;i++) if(!st[i]) dfs_c(i,-1);
unordered_map<int,vector<int>> g;
for(int i=0;i<n;i++){
int a=i,b=edges[i];
if(s.count(a)&&s.count(b)) continue;
g[b].push_back(a);
}
function<void(int)> dfs=[&](int u){
for(auto v:g[u]){
f[v]+=f[u];
dfs(v);
}
};
for(auto i:s) dfs(i);
return f;
}
};