fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long int
  3. #define us unsigned int
  4. #define null 0
  5. #define mod 1000000007
  6. #define m_p make_pair
  7. #define f_i first
  8. #define s_e second
  9. #define p_b push_back
  10.  
  11. using namespace std;
  12.  
  13.  
  14. int coloring(vector<int> v[],bool vis[],int color[],int s)
  15. {
  16.     color[s]=0;
  17.  
  18.     vis[s]=true;
  19.  
  20.     queue<int> q;
  21.  
  22.     q.push(s);
  23.  
  24.     int black=0,white=1;
  25.  
  26.     while(!q.empty())
  27.     {
  28.         int st=q.front();
  29.         q.pop();
  30.  
  31.         for(int i=0;i<(int)v[st].size();i++)
  32.         {
  33.             int curr=v[st][i];
  34.  
  35.             if(vis[curr]==false)
  36.             {
  37.                 if(color[st]==0)
  38.                 {
  39.                     color[curr]=1;
  40.                     black++;
  41.                 }
  42.  
  43.                 else
  44.                 {
  45.                     color[curr]=0;
  46.                     white++;
  47.                 }
  48.  
  49.                 vis[curr]=true;
  50.  
  51.                 q.push(curr);
  52.  
  53.             }
  54.  
  55.         }
  56.  
  57.  
  58.     }
  59.  
  60.     return max(white,black);
  61.  
  62.  
  63. }
  64.  
  65.  
  66.  
  67. int32_t main()
  68. {
  69.  
  70.     int n,m;
  71.  
  72.     cin>>n>>m;
  73.  
  74.     vector<int> v[n*n];
  75.  
  76.     for(int i=0;i<m;i++)
  77.     {
  78.         int x1,y1,x2,y2;
  79.         cin>>x1>>y1>>x2>>y2;
  80.  
  81.         x1--,y1--,x2--,y2--;
  82.         int x=(x1*n)+y1,y=(x2*n)+y2;
  83.  
  84.         v[x].push_back(y);
  85.         v[y].push_back(x);
  86.  
  87.  
  88.     }
  89.  
  90.     bool vis[n*n];
  91.     int color[n*n];
  92.  
  93.     memset(vis,false,sizeof(vis));
  94.  
  95.  
  96.     int ans=0;
  97.  
  98.     for(int i=0;i<n*n;i++)
  99.     {
  100.         if(vis[i]==false)
  101.         {
  102.             ans+=coloring(v,vis,color,i);
  103.         }
  104.     }
  105.  
  106.     cout<<ans<<endl;
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120. }
  121.  
Runtime error #stdin #stdout 0s 4820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cKVuu2
language:
C++14 (gcc 8.3)
created:
3 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!