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

邻接矩阵v[30000][30000]开不出来怎么办?分享一个省空间的模拟存储方法~

Posted by 070220219 at 2010-08-18 10:26:53 on Problem 3107
int head[MN*2],next[MN*2],node[MN*2];
int level[MN];
bool visit[MN];
void addedge(int x,int y)
{
    m++;
    node[m]=y;
    next[m]=head[x];
    head[x]=m;
}
void dfs(int x,int l)
{
    level[x]=l;
    visit[x]=true;
    if(head[x]==-1)
        return ;
    for(int i=head[x];i!=-1;i=next[i]){
        int y=node[i];
        if(!visit[y])
            dfs(y,l+1);
    }
}
while(scanf("%d",&n)!=EOF){
        m=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        memset(visit,false,sizeof(visit));
        dfs(1,1);   //标记节点的层数,以1为跟。
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator