fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. int n,l;
  7. int adj[200][200];
  8. int color[200];
  9. int visited[200];
  10. bool ispipartite=1;
  11. int cntconnected=0;
  12. int cnt=0;
  13. void dfs(int u)
  14. {
  15.     visited[u]=1;
  16.     cntconnected++;
  17.     for(int v=0;v<200;v++)
  18.     {
  19.         if(adj[u][v]&&!visited[v])
  20.         {
  21.             dfs(v);
  22.         }
  23.     }
  24. }
  25. void bfs(int s)
  26. {
  27.     queue <int>q;
  28.     q.push(s);
  29.     color[s]=0;
  30.     while(!q.empty()&&ispipartite)
  31.     {
  32.         int u=q.front();q.pop();
  33.         if(color[u]==0)cnt++;
  34.         for(int v=0;v<200;v++)
  35.         {
  36.             if(adj[u][v])
  37.             {
  38.                if(color[v]==-1){color[v]=1-color[u];q.push(v);}
  39.                else if(color[v]==color[u])
  40.                {
  41.                    ispipartite=0;
  42.                    break;
  43.                }
  44.             }
  45.         }
  46.     }
  47. }
  48. int main()
  49. {
  50.     //freopen("out.txt","w",stdout);
  51.     int Min;
  52.     int T;
  53.     cin>>T;
  54.     int u,v;
  55.     while(T--)
  56.     {
  57.         ispipartite=1;
  58.         Min=0;
  59.         cin>>n;
  60.         memset(adj,0,sizeof adj);
  61.         memset(visited,0,sizeof visited);
  62.         cin>>l;
  63.         for(int i=0;i<l;i++)
  64.         {
  65.             cin>>u>>v;
  66.             adj[u][v]=adj[v][u]=1;
  67.         }
  68.         for(int i=0;i<n;i++)
  69.         {
  70.             if(!visited[i])
  71.             {
  72.                 cntconnected=0;
  73.                 dfs(i);
  74.                 cnt=0;
  75.                 memset(color,-1,sizeof color);
  76.                 bfs(i);
  77.                 if(ispipartite)
  78.                 {
  79.                     if(cntconnected==1)Min+=1;
  80.                     else if(cnt!=0&&cnt<=cntconnected-cnt)Min+=cnt;
  81.                     else Min+=(cntconnected-cnt);
  82.  
  83.                 }
  84.                 else break;
  85.             }
  86.         }
  87.         if(ispipartite)cout<<Min<<endl;
  88.         else cout<<-1<<endl;
  89.     }
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 15384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/11GcsE
language:
C++14 (clang 8.0)
created:
6 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!