Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 大牛帮我看看我的程序为什么超时，是O（n）的啊。

Posted by lujunda at 2012-04-08 11:46:10 on Problem 3107
```#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
int value;
node *next;
node *tail;
}t[100000];
bool mark[100000];
int p[100000],num,n,least;
int dfs(int m)
{
mark[m]=true;
int max=0,sum=0;
struct node *pt;
pt=&t[m];
while(pt->next!=NULL)
{
pt=pt->next;
if(mark[pt->value])
continue;
int temp=dfs(pt->value);
sum+=temp;
max=max>temp?max:temp;
}
sum++;
max=max>n-sum?max:n-sum;
if(least==max)
p[num++]=m;
else if(least>max)
{
least=max;
num=0;
p[num++]=m;
}
return sum;
}
{
node *pt;
pt=new node;
pt->value=value;
pt->next=NULL;
t[m].tail->next=pt;
t[m].tail=pt;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<100000;i++)
mark[i]=false;
num=0;
least=100000;
for(int i=0;i<100000;i++)
t[i].tail=&t[i];
for(int i=0,temp_1,temp_2;i<n-1;i++)
{
scanf("%d%d",&temp_1,&temp_2);
}
dfs(1);
sort(p,p+num);
for(int i=0;i<num;i++)
{
if(i)
printf(" %d",p[i]);
else
printf("%d",p[i]);
}
printf("\n");
system("pause");
}```

Followed by: