UVA 11080 Solution- Place the Guards
/*uva 11080 Solution -Place the Guards
uva id: shoaib05
Accepted Time: 0.004
*/
#include<stdio.h>
enum{BLACK,RED,BLUE};
enum boolean{false,true};
int red,blue,color[205],node,table[205][205],ans,queue[205],front,rear;
enum boolean impossible;
void push(int x)
{
queue[rear]=x;
rear++;
if(rear==205)
rear=0;
}
int pop()
{
int x;
x=queue[front];
front++;
if(front==205)
front=0;
return x;
}
void bfs(int x)
{
int i,cur,len,col;
push(x);
while(front!=rear)
{
cur=pop();
len=table[cur][0];
col=color[cur]==RED?BLUE:RED;
for(i=1;i<=len;i++)
{
x=table[cur][i];
if(color[x]==BLACK)
{
push(x);
if(col==RED)
{
color[x]=RED;
red++;
}
else
{
color[x]=BLUE;
blue++;
}
}
else if(color[cur]==color[x])
{
impossible=true;
return;
}
}
}
}
int main()
{
int test,i,j,e,x,y;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&node,&e);
for(i=0;i<node;i++)
{
table[i][0]=0;
color[i]=BLACK;
}
ans=0;
front=0;
rear=0;
while(e--)
{
scanf("%d %d",&x,&y);
table[x][0]++;
j=table[x][0];
table[x][j]=y;
table[y][0]++;
j=table[y][0];
table[y][j]=x;
}
impossible=false;
for(i=0;i<node;i++)
{
if(color[i]==BLACK)
{
color[i]=RED;
if(table[i][0]==0)
{
ans++;
}
else
{
red=1;
blue=0;
bfs(i);
if(impossible)
{
ans=-1;
break;
}
else
{
ans+=red<blue?red:blue;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
uva id: shoaib05
Accepted Time: 0.004
*/
#include<stdio.h>
enum{BLACK,RED,BLUE};
enum boolean{false,true};
int red,blue,color[205],node,table[205][205],ans,queue[205],front,rear;
enum boolean impossible;
void push(int x)
{
queue[rear]=x;
rear++;
if(rear==205)
rear=0;
}
int pop()
{
int x;
x=queue[front];
front++;
if(front==205)
front=0;
return x;
}
void bfs(int x)
{
int i,cur,len,col;
push(x);
while(front!=rear)
{
cur=pop();
len=table[cur][0];
col=color[cur]==RED?BLUE:RED;
for(i=1;i<=len;i++)
{
x=table[cur][i];
if(color[x]==BLACK)
{
push(x);
if(col==RED)
{
color[x]=RED;
red++;
}
else
{
color[x]=BLUE;
blue++;
}
}
else if(color[cur]==color[x])
{
impossible=true;
return;
}
}
}
}
int main()
{
int test,i,j,e,x,y;
scanf("%d",&test);
while(test--)
{
scanf("%d %d",&node,&e);
for(i=0;i<node;i++)
{
table[i][0]=0;
color[i]=BLACK;
}
ans=0;
front=0;
rear=0;
while(e--)
{
scanf("%d %d",&x,&y);
table[x][0]++;
j=table[x][0];
table[x][j]=y;
table[y][0]++;
j=table[y][0];
table[y][j]=x;
}
impossible=false;
for(i=0;i<node;i++)
{
if(color[i]==BLACK)
{
color[i]=RED;
if(table[i][0]==0)
{
ans++;
}
else
{
red=1;
blue=0;
bfs(i);
if(impossible)
{
ans=-1;
break;
}
else
{
ans+=red<blue?red:blue;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
Comments
Post a Comment