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 |
这道题给的数据有点水啊数据水啊,在自己学校的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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator