## 11080 - Place the Guards

Moderator: Board moderators

andre_abrantes
New poster
Posts: 3
Joined: Mon Jun 05, 2006 4:44 am
Location: Rio de Janeiro, Brasil
Hello everyone!
I've tried all the input avaliable in this thread and my code seems to work with them, except for that one from mamud, I think, where there are edges that connect vertexes beyond the limit previously given.
Anyway, I just keep getting WA.
Here is my code, can anyone tell me where is my mistake!?

Code: Select all

``````Corrected and accepted!
Thanks to Martin Macko.
``````
Last edited by andre_abrantes on Sun Sep 10, 2006 11:36 pm, edited 1 time in total.
Andr
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
andre_abrantes wrote:Hello everyone!
I've tried all the input avaliable in this thread and my code seems to work with them, except for that one from mamud, I think, where there are edges that connect vertexes beyond the limit previously given.
Anyway, I just keep getting WA.
Here is my code, can anyone tell me where is my mistake!?
Not working for:

Code: Select all

``````1
5 6
0 1
0 2
1 3
2 3
4 0
5 0``````

Code: Select all

``2``
andre_abrantes
New poster
Posts: 3
Joined: Mon Jun 05, 2006 4:44 am
Location: Rio de Janeiro, Brasil
Thank you Martin Macko.
I found out that my code could push the same vertex twice or more in the queue.
Andr
max_zd
New poster
Posts: 2
Joined: Tue Apr 10, 2007 2:51 pm

### Help!

Is there anybody who can help me?

I think my algorithm is correct, but keeps get WA.

My algoirthm:
1. Process each connected components("CC") one by one
2. For each CC, if there is only one vertex belongs to it, then the answer is increased by 1. if there are more than one vertex belong to it, we check if it is a bipartite graph, if not, we assert that the problem is no solution. otherwise, we count the number of vertices in set X and set Y. obviously, we choose the smaller between them.

Here is my code.

Code: Select all

``````#include <cstdio>
#include <cstring>

const	int		limit_size	=	200	+	10;

int			n , m;
bool			mat	[ limit_size ][ limit_size ];
int			cnt	[ 2 ];

void	init()
{
int		i , a , b;

memset(mat , 0 , sizeof(mat));

scanf("%d%d" , &n , &m);
for(i = 0; i < m; i ++)
{
scanf("%d%d" , &a , &b);
mat[a][b] = mat[b][a] = 1;
}
}

bool			mark	[ limit_size ];
int			color	[ limit_size ];
int			queue	[ limit_size ];

bool	check()
{
int		i , j;

for(i = 0; i <= tail; i ++)
for(j = i + 1; j <= tail; j ++)
if( mat[ queue[i] ][ queue[j] ] && color[ queue[i] ] == color[ queue[j] ] ) return 0;
return 1;
}

void	solve()
{
int		i , u , v;
int		ret = 0;

memset(mark , 0 , sizeof(mark));

for(i = 0; i < n; i ++)
if(! mark[i])
{
cnt[0] = cnt[1] = 0;

queue[ head = tail = 0 ] = i;
mark[i] = 1; color[i] = 0; cnt[0] = 1;

{
u = queue[ head ++ ];

for(v = 0; v < n; v ++)
if(mat[u][v] && ! mark[v])
{
queue[ ++ tail ] = v;
mark[v] = 1; color[v] = 1 - color[u]; cnt[ color[v] ] ++;
}
}

if(tail == 0)
{
ret ++; continue ;
}

if(! check())
{
printf("-1"); return ;
}
ret += cnt[0] <? cnt[1];
}

printf("%d\n" , ret);
}

int	main()
{
int		cnt_case;

for(scanf("%d" , &cnt_case); cnt_case --;)
{
init();
solve();
}

return 0;
}
``````
windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### Re: Help!

max_zd wrote:

Code: Select all

``````
if(! check())
{
printf("-1"); return ;
}
``````
You should modifiy printf("-1") to printf("-1\n")
THis works
Ratul Ahmed
New poster
Posts: 4
Joined: Mon Aug 30, 2010 3:40 am

### 11080 - Place the Guards

simple Bipertite graph problem...

1) make 2 sets of vertex for each sub-graph or graph
2) take the minimum vertices from each of those sets & sum it
3) check how many vertices has no adjacent (help the king to find the minimum number of guards needed to guard all the junctions and streets of his country. )
Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11080 : algorithm

Cut after Accepted !!!
alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

### Re: 11080 : algorithm

One more tip, the input may not contain edges for all vertexes, so vertexes with grade = 0 should be counted to the answer.
vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 11080 : algorithm

Some useful test cases

Input

Code: Select all

``````1
5 3
0 1
3 2
2 1
``````
Output

Code: Select all

``3``
Input

Code: Select all

``````1
1 0``````
Output

Code: Select all

``1``
Output is 3 because junction 4 needs to be guarded as well and other than that you can place guards at 0 and 2.

To solve this problem just check if it is bipartite or not? But remember that graph could be disconnected so you will have to take that into account as well. Now if a graph is bipartite, just count the nodes in both subsets and choose the miminum. I used distances (even and odd) to divide the graph into two sets of nodes.
samir_h
New poster
Posts: 11
Joined: Wed Mar 18, 2015 8:47 am

### 11080 - Place the Guards[uDebug output different for TC sequence change]

In uDebug getting different output if we change the test case sequence.
For example: input [2, input#1, input#2] = output[o#1, o#2] but input[2, input#2, input#1] giving output[o#2, o#3]
Why ?

--------------------------------------------------------------
Input:
2

5 6
0 1
0 2
1 3
2 3
4 0
5 0

13 12
0 8
1 8
2 9
3 9
4 10
5 10
6 11
7 11
8 12
9 12
10 12
11 12

Output:
2
4
--------------------------------------------------------------
Input(replace 2nd input with 1st input):
2

13 12
0 8
1 8
2 9
3 9
4 10
5 10
6 11
7 11
8 12
9 12
10 12
11 12

5 6
0 1
0 2
1 3
2 3
4 0
5 0

Output:
4
-1

--------------------------------------------------------------
samir_h
New poster
Posts: 11
Joined: Wed Mar 18, 2015 8:47 am

### Re[Ratul Ahmed]: 11080 - Place the Guards

Hello Ratul Ahmed,