posts - 64, comments - 4, trackbacks - 0, articles - 0

hdu_3478

Posted on 2010-08-19 23:19 acronix 阅读(255) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理