C++

Forum

 
 
Bipartite graph

ankur12106037 (22)
Question ->http://www.spoj.com/problems/BUGLIFE/
In this question we are given number of bugs and their interactions we have to check that there should not be interaction b/w same sex.So basically we have to check if the graph given is bipartite or not. I have used the coloring concept that is if we can color the graph with the two different colors then the graph will be bipartite graph.I tested my code for many cases it is giving right output but giving wrong answer on SPOJ.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
#include<map>
#include<stdio.h>
#define gc getchar
using namespace std;


void inline input(long int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc())
        {x = (x<<1) + (x<<3) + c - 48;}
}


int main()
{
    long int t,n,in,dup;
    map<long int,char> c;
    map<long int,char>::iterator j;
    multimap<long int,long int> m;
    multimap<long int,long int>::iterator i;
    input(t); dup=t;
    long int u,v;
    bool flag;
    while(t--)
    {
       input(n);
       input(in);
       while(in--)
       {
           input(u);
           input(v);
           c[u]='x';  //initially assigning color x to all
           c[v]='x';
           m.insert(std::pair<long int,long int>(u,v));
       }
       flag=1;

       for(i=m.begin();i!=m.end();i++)
       {
           if(c[i->first]=='x'&&c[i->second]=='x')
           {
               c[i->first]='b';
               c[i->second]='g';
           }
           else if(c[i->first]=='x'&&c[i->second]=='b')
           {
               c[i->first]='g';
           }
           else if(c[i->first]=='b'&&c[i->second]=='x')
           {
               c[i->second]='g';
           }
           else if(c[i->first]=='x'&&c[i->second]=='g')
           {
               c[i->first]='b';
           }
           else if(c[i->first]=='g'&&c[i->second]=='x')
           {
               c[i->second]='b';
           }
           else if(c[i->first]=='b'&&c[i->second]=='g')
           {
               continue;
           }
           else if(c[i->first]=='g'&&c[i->second]=='b')
           {
               continue;
           }
           else if(c[i->first]=='b'&&c[i->second]=='b')
           {

               flag=0;break; //not bipartite
           }
           else if(c[i->first]=='g'&&c[i->second]=='g')
           {
               flag=0;break; //not bipartite
           }

        }

        printf("Scenario #%ld:",dup-t);
        if(flag)
        {
                printf("\nNo suspicious bugs found!\n");
        }
        else
        {
            printf("\nSuspicious bugs found!\n");
        }
        m.clear();
        c.clear();
    }

    return 0;

}

cire (8284)
Consider the following input file:

1
5 4
1 5
2 4
3 2
3 5


where the values could be:

1 - b
2 - g
3 - b
4 - b
5 - g


which would make the scenarios look like:
1 5  -  b g
2 4  -  g b
3 2  -  b g
3 5  -  b g


so, "No suspicious bugs found" should be output. Your code outputs the opposite. Do you see why?

ankur12106037 (22)
Thanks Cire .
I got the problem.
Topic archived. No new replies allowed.