11080 - Place the Guards

[andre_abrantes]

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.

Thanks in advance.

[Martin Macko]

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

The correct answer:

Code: Select all

2

[andre_abrantes]

Thank you Martin Macko.
I found out that my code could push the same vertex twice or more in the queue.

[max_zd]

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 ];
int			head , tail;

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;

			while(head <= tail)
			{
				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]

Code: Select all

			if(! check())
			{
				printf("-1"); return ;
			}

You should modifiy printf("-1") to printf("-1\n")
THis works

[Ratul Ahmed]

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. )
4) sum it with answer

[Mukit Chowdhury]

Cut after Accepted !!!

[alexiago]

One more tip, the input may not contain edges for all vertexes, so vertexes with grade = 0 should be counted to the answer.

[vsha041]

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]

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]

Hello Ratul Ahmed,
I followed your approach:
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. )
4) sum it with answer

But still Wrong Answer.
My code: http://ideone.com/fork/QQgE7x

Can any one suggest what is wrong ?