幫忙修改,一直TLE
#include <bits/stdc++.h>
using namespace std;
int parent[100005],high[100005];
void find_high(int n){
while(parent[n]){
if(high[parent[n]]>=high[n]+1)
return;
high[parent[n]]=high[n]+1;
n=parent[n];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,k,son;
while(cin>>n){
memset(high,0,sizeof(high));
memset(parent,0,sizeof(parent));
for(int i=1;i<=n;i++){
cin>>k;
for(int j=0;j<k;j++){
cin>>son;
parent[son]=i;
}
}
for(int i=1;i<=n;i++)
if(!parent[i]){
cout<<i<<'\n';
break;
}
for(int i=1;i<=n;i++)
find_high(i);
int sum=0;
for(int i=1;i<=n;i++)
sum+=high[i];
cout<<sum<<'\n';
}
return 0;
}
幫忙修改,一直TLE
#include <bits/stdc++.h>
using namespace std;
int parent[100005],high[100005];
void find_high(int n){
while(parent[n]){
if(high[parent[n]]>=high[n]+1)
return;
high[parent[n]]=high[n]+1;
n=parent[n];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,k,son;
while(cin>>n){
memset(high,0,sizeof(high));
memset(parent,0,sizeof(parent));
for(int i=1;i<=n;i++){
cin>>k;
for(int j=0;j<k;j++){
cin>>son;
parent[son]=i;
}
}
for(int i=1;i<=n;i++)
if(!parent[i]){
cout<<i<<'\n';
break;
}
for(int i=1;i<=n;i++)
find_high(i);
int sum=0;
for(int i=1;i<=n;i++)
sum+=high[i];
cout<<sum<<'\n';
}
return 0;
}
當圖為一條鍊時你的算法為O(n^2)