Posted on 2010-08-19 23:19
acronix 阅读(271)
评论(0) 编辑 收藏 引用 所属分类:
qqy解题报告
//考察点: 着色原理 BFS 邻接表建图
//思路: 先BFS,在BFS的过程中标记到达某点时的步数的奇偶性.
//提交情况: 3WA 1AC
第一次WA是因为判断是否相连的时候就错了 后来的两次WA是因为没有初始化VIS数组,这个是我的老毛病了要更正!
//收获: 学习到了用邻接表建图的皮毛 熟悉了用邻接表去建一个图的方法
//经验: 写好代码以后一定要想象一下处理每个CASE都用到了哪些东西 用完之后都要想是不是需要初始化.!!!!很重要的一个习惯. 要养成这种好的编程习惯.
// ACcode
#include<memory.h>
#include<stdio.h>
#include<stdlib.h>
#define VN 100000
#define EN 500000
struct node
{
int v;
int nxt;
};
node mem[VN+EN+10];
int head[VN+1];
int cnt = 1;
int n,m,s;
int mark[VN];
void addedge(int u, int v)
{
mem[cnt].v = v;
mem[cnt].nxt = head[u];
head[u] = cnt++;
}
int que[2*VN];
bool vis[VN];
int fore,tail;
bool bfs()
{
bool flag = false;
int i,j,count[VN]= {0};
fore = tail = 0;
que[tail ++] = s;
vis[s] = true;
count[s] = 0;
mark[s] = 0;
while(fore < tail)
{
j = que[fore ++];
int p = head[j];
while(p != 0)
{
i = mem[p].v;
{
if(!vis[i])
{
vis[i] = true;
count[i] = count[j] + 1;
mark[i] = count[i] % 2;
que[tail ++] = i;
}
else if(vis[i])
{
if(mark[i] == mark[j]) flag = true;
}
}
p = mem[p].nxt;
}
}
return flag;
}
int main()
{
int T,i,j,k,t,p;
int u,v;
memset(mark,-1,sizeof(mark));
scanf("%d",&T);
for(i = 1; i <= T; i ++)
{
scanf("%d%d%d",&n,&m,&s);
for(j = 0; j < m; j++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
bool s1,s2;
s1 = bfs();
s2 = true;
for(int k = 0; k < n; k++)
{
if(vis[k] == false) {s2 = false;break;}
}
printf("Case %d: ",i);
if(s1 && s2) printf("YES\n");
else printf("NO\n");
memset(head,0,sizeof(head));
memset(mem,0,sizeof(mem));
memset(mark,-1,sizeof(mark));
memset(vis,0,sizeof(vis));
cnt = 1;
}
return 0;
}