| ||||||||||
| 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