OJ Board

Posted: **Thu Sep 07, 2006 8:11 pm**

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.

Posted: **Sat Sep 09, 2006 8:48 pm**

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

The correct answer:

Code: Select all

Posted: **Sun Sep 10, 2006 11:37 pm**

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

Posted: **Tue Apr 10, 2007 3:06 pm**

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;
}

Posted: **Sun Apr 29, 2007 4:17 am**

max_zd wrote:

Code: Select all


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

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

Posted: **Fri Mar 04, 2011 2:36 pm**

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

Posted: **Mon Oct 01, 2012 1:49 pm**

Cut after Accepted !!!

Posted: **Wed Aug 14, 2013 7:05 pm**

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

Posted: **Thu Mar 20, 2014 9:54 pm**

Some useful test cases

Input

Code: Select all

Output

Code: Select all

Input

Code: Select all

1
1 0

Output

Code: Select all

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.

Posted: **Fri Mar 25, 2016 12:03 pm**

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

--------------------------------------------------------------

Posted: **Fri Mar 25, 2016 12:06 pm**

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 ?

OJ Board

11080 - Place the Guards

Help!

Re: Help!

11080 - Place the Guards

Re: 11080 : algorithm

Re: 11080 : algorithm

Re: 11080 : algorithm

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

Re[Ratul Ahmed]: 11080 - Place the Guards