fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define lli long long int
  3. using namespace std;
  4. lli mat[1002][1002];
  5. lli visited[10000];
  6. lli color[10000];
  7. lli isbipartaite(lli  src,lli n)
  8. {
  9.   queue<lli> q;
  10.   while(!q.empty())
  11.   q.pop();
  12.   q.push(src);
  13.   color[src]=1;
  14.   while(!q.empty())
  15.   {
  16.     lli x=q.front();
  17.     q.pop();
  18.     visited[x]=1;
  19.     for(lli v=0;v<n;v++)
  20.     {
  21.        if(mat[x][v]!=0 && color[v]==-1)
  22.        {
  23.           color[v]=1-color[x];
  24.           q.push(v);
  25.        }
  26.        else if(mat[x][v]!=0 && color[v]==color[x])
  27.          return false;
  28.     }
  29.   }
  30.   return true;
  31. }
  32.  
  33. int main()
  34. {
  35.   lli t;
  36.   scanf("%lld",&t);
  37.   while(t--)
  38.   {
  39.     lli n,m;
  40.     scanf("%lld%lld",&n,&m);
  41.     for(lli i=0;i<n;i++)
  42.     {
  43.        memset(mat[i],n,sizeof(lli));
  44.     }
  45.     for(lli i=0;i<m;i++)
  46.     {
  47.        lli a,b;
  48.        scanf("%lld%lld",&a,&b);
  49.        a--;b--;
  50.        mat[a][b]=1;mat[b][a]=1;
  51.     }
  52.     for(lli i=0;i<n;i++)
  53.     {
  54.       for(lli j=0;j<n;j++)
  55.       {
  56.         if(i==j)
  57.         {
  58.           mat[i][j]=0;
  59.           continue;
  60.         }
  61.         mat[i][j]=!mat[i][j];
  62.       }
  63.     }
  64.     for(lli i=0;i<n;i++)
  65.     {
  66.        visited[i]=0;
  67.     }
  68.     lli c=1;
  69.     lli flag=1,x;
  70.     for(lli i=0;i<n;i++)
  71.       color[i]=-1;
  72.     for(lli i=0;i<n;i++)
  73.     {
  74.        if(visited[i]==0)
  75.            x=isbipartaite(i,n);
  76.        if(x==0)
  77.         flag=0;
  78.     }
  79.     if(flag==0)
  80.       printf("NO\n");
  81.     else
  82.       printf("YES\n");
  83.  
  84.   }
  85. }
  86.  
Runtime error #stdin #stdout 0s 11472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sRJFio
language:
C++ (gcc 8.3)
created:
9 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!