fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<vector>
  4. #include<queue>
  5. using namespace std;
  6. int color[100001];
  7. vector<vector<int > > myvector (100001);
  8. vector<int> color1;
  9. vector<int> color2;
  10. queue<int> myq;
  11.  
  12. int main()
  13. {
  14.     int n;
  15.     scanf("%d",&n);
  16.  
  17.  
  18.     int m;
  19.     scanf("%d",&m);
  20.  
  21.     int s=m;
  22.     while(m--)
  23.         {
  24.             int a,b;
  25.             scanf("%d%d",&a,&b);
  26.             myvector[a].push_back(b);
  27.             myvector[b].push_back(a);
  28.         }
  29.  
  30.     int size1=0;
  31.     int size2=0;
  32.  
  33.     int i;
  34.  
  35.     for(i=1;i<n+1;i++)
  36.         {
  37.             if (color[i]!=0)
  38.             continue;
  39.  
  40.             if (myvector[i].size()==0)
  41.                 continue;
  42.  
  43.             color[i]=1;
  44.             color1.push_back(i);
  45.             size1++;
  46.             myq.push(i);
  47.  
  48.         while(!myq.empty())
  49.         {
  50.             int p=myq.front();
  51.             myq.pop();
  52.             for(i=0;i<myvector[p].size();i++)
  53.                 {
  54.                     if (color[myvector[p][i]]==0)
  55.                         {
  56.                         if (color[p]==1)
  57.                             {size2++;
  58.                             color2.push_back(myvector[p][i]);
  59.                             color[myvector[p][i]]=2;
  60.                             }
  61.                         else
  62.                             {size1++;
  63.                             color[myvector[p][i]]=1;
  64.                             color1.push_back(myvector[p][i]);
  65.                             }
  66.                         myq.push(myvector[p][i]);
  67.  
  68.                         }
  69.                     else if (color[myvector[p][i]]==color[p])
  70.                         {
  71.  
  72.                             printf("-1\n");
  73.                             return 0;
  74.                         }
  75.  
  76.                 }
  77.  
  78.         }
  79.  
  80.         }
  81.  
  82.     printf("%d\n",size1);
  83.  
  84.     for(vector<int>  :: iterator it=color1.begin();it!=color1.end();++it)
  85.         {
  86.             printf("%d ",(*it));
  87.         }
  88.  
  89.     printf("\n");
  90.     printf("%d\n",size2);
  91.  
  92.      for(vector<int> ::iterator it=color2.begin();it!=color2.end();++it)
  93.         {
  94.             printf("%d ",(*it));
  95.         }
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.     return 0;
  105. }
  106.  
Runtime error #stdin #stdout 0s 5024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eKwgjv
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!