10505  Montesco vs Capuleto
Moderator: Board moderators
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?
Thanks in advance,
Witto
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

 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.
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.
Solved...
I was missing out something in the vertex coloring process....
I rewrote the function and got accepted.
Many thanks.
I rewrote the function and got accepted.
Many thanks.
[]'s
Witto
Witto

 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?
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?
Re: My guess
What about the input?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
Hello windows2k,
The output of my program for this input is:
I used the algorithm that witto wrote above.
The output of my program for this input is:
Code: Select all
0
1
1
[]'s
Lucindo
Lucindo
Re: My guess
The output of my solution for that input is:windows2k wrote:What about the input?lucindo wrote:My accepted program outpus '0' for this input
3
(...)
thx
Code: Select all
0
2
2
[]'s
Witto
Witto
Re: My guess
The output of my solution for that input is:
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,1cn)) 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]
Code: Select all
0
2
2
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,1cn)) 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]
hmm.. the code above
I think you just made a mistake//
variable t is simply duplicated.
variable t is simply duplicated.
Re: hmm.. the code above
I don't understand your meaninghuksy wrote:I think you just made a mistake//
variable t is simply duplicated.
Could you explain more clearly , thx