10505 - Montesco vs Capuleto

Moderator: Board moderators

witto
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

10505 - Montesco vs Capuleto

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?

Witto

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

Solved...

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

Many thanks.
[]'s
Witto

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Is input correct?

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
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

My guess

My accepted program outpus '0' for this input
[]'s

Lucindo

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: My guess

lucindo wrote:My accepted program outpus '0' for this 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
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:
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.
[]'s

Lucindo

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
lucindo wrote: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
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:

Re: My guess

windows2k wrote:
lucindo wrote:My accepted program outpus '0' for this input
3
(...)
thx
The output of my solution for that input is:

Code: Select all

``````0
2
2
``````
Good Luck
[]'s
Witto

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: My guess

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
New poster
Posts: 5
Joined: Fri Jan 18, 2002 2:00 am
Location: Sao Paulo - Brazil
Contact:
Try doing a BFS insted of DFS... it worked for me.
[]'s
Witto

huksy
New poster
Posts: 3
Joined: Sun Jul 13, 2003 7:00 pm

hmm.. the code above

I think you just made a mistake//

variable t is simply duplicated.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: hmm.. the code above

huksy wrote:I think you just made a mistake//

variable t is simply duplicated.
Could you explain more clearly , thx

huksy
New poster
Posts: 3
Joined: Sun Jul 13, 2003 7:00 pm
outer while lv t & inner t

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
huksy wrote:outer while lv t & inner t
I have modified my code,but still get WA.
Maybe there exists some trick input? @@