10505 - Montesco vs Capuleto

[witto]

What should be the output for this input:
1

2
0
1 5

It seems that the judge input has something like that.
I've put an assert() to check that.

As for the algorithm, I'm trying to find all the bipartite components of the graph build from input and inviting the people from the bigger set of each bipartition. Does that solve the problem?


Thanks in advance,
Witto

[Adrian Kuegel]

You can ignore the numbers >n (it makes no difference if you do it or not if your algorithm is correct).
When you search for bipartite components, and you find out that they are not bipartite, do you mark all nodes in the component so that you don't use them again? That was my mistake.
If I understand your algorithm, it should solve the problem.

[witto]

I was missing out something in the vertex coloring process....
I rewrote the function and got accepted.

Many thanks.

[Alexander Kozlov]

Is this input correct?

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

If YES what sould be the answer: 0 or 3?

[lucindo]

My accepted program outpus '0' for this input

[windows2k]

My accepted program outpus '0' for this input

What about the input?
3

6
1 2
2 3 1
1 4
2 1 2
3 1 2 3
1 1

6
2 23
1 3
1 1
1 6
1 4
0

8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0

thx

[lucindo]

Hello windows2k,

The output of my program for this input is:

Code: Select all

0
1
1

I used the algorithm that witto wrote above.

[windows2k]

Hello windows2k,

The output of my program for this input is:
1
[/code]

I used the algorithm that witto wrote above.

Can you tell me why the ans is 1
8
2 2 4
1 3
1 4
0
3 6 7 8
2 7 8
1 8
0

if i choose 1 and 3 or 2 and 4,we can choose two
or i misunderstanding the meaning?

[witto]

My accepted program outpus '0' for this input

What about the input?
3
(...)
thx

The output of my solution for that input is:

Code: Select all

0
2
2

Good Luck

[windows2k]

The output of my solution for that input is:

Code: Select all

0
2
2

Good Luck[/quote]
To witto,My program outputs the same result
But I get WA:(
Could someone tell me what's wrong
[cpp]
#include <stdio.h>
#include <string.h>
bool graph[201][201];
char color[201];
int cc[2];
int n;
bool DFS(int node,int cn)
{
color[node]=cn;
cc[cn]++;
for(int i=1;i<=n;i++)
if(graph[node])
{
if(color==cn) return false;
if(color==-1)
{
if(!DFS(i,1-cn)) return false;
}
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(graph,false,sizeof(graph));
memset(color,0xff,sizeof(color));
for(int i=1;i<=n;i++)
{
int l,t;
scanf("%d",&l);
for(int j=0;j<l;j++)
{
scanf("%d",&t);
graph[t]=graph[t]=true;
}
}
int ans=0;
for(int i=1;i<=n;i++)
if(color==-1)
{
cc[0]=cc[1]=0;
if(!DFS(i,0)) continue;
if(cc[0]>cc[1]) ans+=cc[0];
else ans+=cc[1];
}
printf("%d\n",ans);
}
return 0;
}
[/cpp]

[witto]

Try doing a BFS insted of DFS... it worked for me.

[huksy]

I think you just made a mistake//

variable t is simply duplicated.

[windows2k]

I think you just made a mistake//

variable t is simply duplicated.

I don't understand your meaning
Could you explain more clearly , thx

[huksy]

outer while lv t & inner t

[windows2k]

outer while lv t & inner t

I have modified my code,but still get WA.
Maybe there exists some trick input? @@