fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define REP(p,a,b) for(int p=a;p<b;p++)
  6. #define REPR(p,a,b) for(int p=a;p>=b;p--)
  7. #define MOD 1000000007
  8. #define pb(f) push_back(f)
  9. #define mkp(a,b) make_pair(a,b)
  10. #define pii pair<int,int>
  11. #define IOS ios_base::sync_with_stdio(false); cin.tie(0);
  12.  
  13.  
  14. int n,m;
  15. vector<int> adj[100005];
  16. int color[100005];
  17. vector<int> odd,even;
  18.  
  19. bool isBipartite(int x){
  20.  
  21.     color[x] = 1;
  22.     queue <int> q;
  23.     q.push(x);
  24.     int cnt=0;
  25.     while (!q.empty()){
  26.         int sz=q.size();
  27.         while(sz--){
  28.             int u = q.front();
  29.             if(cnt&1) odd.push_back(u);
  30.             else even.push_back(u);
  31.             q.pop();
  32.             REP(i,0,adj[u].size()){
  33.                 int v=adj[u][i];
  34.                 if (color[v] == -1){
  35.                     color[v] = 1 - color[u];
  36.                     q.push(v);
  37.                 }
  38.                 else if (color[v] == color[u])
  39.                     return false;
  40.             }
  41.         }
  42.         cnt++;
  43.     }
  44.     return true;
  45. }
  46.  
  47. int main(){
  48.     //FREI("input.txt");
  49.     //FREO("output.txt");
  50.     IOS;
  51.     //citi;
  52.     int x,y;
  53.     bool f=0;
  54.     cin>>n>>m;
  55.     REP(i,0,m){
  56.         cin>>x>>y;
  57.         adj[x].pb(y);
  58.         adj[y].pb(x);
  59.     }
  60.     memset(color,-1,sizeof(color));
  61.     REP(i,1,n+1){
  62.         if(color[i]==-1){
  63.             if(!isBipartite(i)){
  64.                 f=1;
  65.                 break;
  66.             }
  67.         }
  68.     }
  69.     if(!f){
  70.         cout<<odd.size()<<endl;
  71.         REP(i,0,odd.size())
  72.             cout<<odd[i]<<" ";
  73.         cout<<endl;
  74.         cout<<even.size()<<endl;
  75.         REP(i,0,even.size())
  76.             cout<<even[i]<<" ";
  77.         cout<<endl;
  78.     }
  79.     else cout<<"-1\n";
  80.     return 0;
  81. }
Success #stdin #stdout 0s 4972KB
comments (?)
stdin 
Standard input is empty
stdout 
0

0
https://ideone.com/PwduxV
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!