| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大牛帮我看看我的程序为什么超时,是O(n)的啊。#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;
}
void add(int m,int value)
{
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);
add(temp_1,temp_2);
add(temp_2,temp_1);
}
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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator