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

这道题给的数据有点水啊

Posted by yangheyu at 2012-09-28 08:52:30 on Problem 3660
数据水啊,在自己学校的OJ用邻接表建图并深搜死活过不了啊,求大牛指点啊。
思路:用邻接表建图,之后循环对图上每个点做起始点进行深搜,如果搜到某个其他点,证明这两个点有关联,进行记录。最后查找与这个点有关联的点的个数来确定这个点是否位置确定。不知代码哪里出了问题,求大牛指点(在POJ能AC,但是自己学校的WA)
#include<stdio.h>
struct Edges{int end,next;}eg[10000];
int head[10000],num[305],i,j,n,m,st,nd,pot,number;
bool sp[305];
void build(int a,int b)
{
    eg[pot].end=b;
    eg[pot].next=head[a];
    head[a]=pot++;
}
void DFS(int a)
{
    if(!sp[a]) return ;
    sp[a]=false;
    if(i!=a) num[a]++;
    num[i]++;
    for(int k=head[a];k!=-1;k=eg[k].next) DFS(eg[k].end);
}
int main(void)
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(i=0;i<305;i++)
        {
            num[i]=0;
            head[i]=-1;
        }
        pot=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&st,&nd);
            build(nd,st);
        }
        for(i=1;i<=m;i++)
        {
            for(j=0;j<305;j++) sp[j]=true;
            DFS(i);
        }
        for(i=1;i<=m;i++)
        {
            //printf("num=%d\n",num[i]);
            if(num[i]==m) number++;
        }
        printf("%d\n",number);
    }
    return 0;
}



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