INTERVIEWBIT/BipartiteOrNot.cpp at master · kaint/INTERVIEWBIT · GitHub

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
#include<bits/stdc++.h>
using namespace std ;
vector<int>*graph;

int bipartite(int n)
{
    unordered_set<int>sets[2] ;

    if(n==0)
        return 1 ;

    sets[0].insert(0) ;

    vector<int>pending ;
    pending.push_back(0) ;

    while(pending.size()>0)
    {
       int current=pending.back()  ;
       pending.pop_back()  ;

       for(int i=0;i<graph[current].size() ;i++)
       {
           int neighbor=graph[current][i] ;
           int current_set=sets[0].count(current)==0?1:0 ;

           if(sets[0].count(neighbor)==0&&sets[1].count(neighbor)==0)
           {
               sets[current_set^1].insert(neighbor) ;
               pending.push_back(neighbor) ;

           }
           else if(sets[current_set].count(neighbor)>0)
            return 0;


       }
    }
    return 1 ;


}

int main()
{
  int n,m;
  cin>>n>>m ;

  graph=new vector<int>[n] ;

  while(m--)
  {
\
      int a,b;
      cin>>a>>b;
      graph[a].push_back(b) ;
      graph[b].push_back(a) ;
  }
  if(bipartite(n))
       {
           cout<<"Yes"<<endl;
       }
       else
       cout<<"Not"<<endl;


}