SHARE
TWEET

Untitled

a guest Jan 21st, 2020 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int deg[101];
  6. int mas[101][101];
  7. int d[101];
  8.  
  9. void dfs(int x){
  10.   d[x]=1;
  11.   int i=1;
  12.   while(i<=100){
  13.     if((mas[i][x]==1) && (d[i]!=1)) dfs(i);
  14.     i++;
  15.   }
  16. }
  17.  
  18. int main(){
  19.     ios::sync_with_stdio(false);
  20.     cin.tie(0);
  21.     int n,m,p,q;
  22.     int a,b;
  23.     cin >> m;
  24.     cin >> n;
  25.     for(int i=1; i<=n; i++){
  26.         cin >> a >> b;
  27.         mas[a][b]=1;
  28.         mas[b][a]=1;
  29.  
  30.     }
  31.     for(int i=1; i<=m; i++){
  32.         for(int j=1; j<=m; j++){
  33.             mas[i][j]=1-mas[i][j];
  34.         }
  35.     }
  36.  
  37.     for(int i=1; i<=m; i++){
  38.         for(int j=1; j<=m; j++){
  39.             if(i!=j) deg[i]=(deg[i]+mas[i][j])%2;
  40.         }
  41.     }
  42.  
  43.     int s=0;
  44.     for(int i=1; i<=m; i++){
  45.         s=s+deg[i];
  46.     }
  47.     s=s/2;
  48.     p=0;
  49.     for(int i=1; i<=m; i++){
  50.         for(int j=1; j<=m; j++){
  51.             if((deg[i]==1) && (deg[j]==1)){
  52.                 mas[i][j]=1;
  53.                 mas[j][i]=1;
  54.                 p=1;
  55.             }
  56.         }
  57.     }
  58.  
  59.     int c=0;
  60.     for(int j=1; j<=m; j++){
  61.         if(d[j]==0){
  62.             c++;
  63.             //for(int i=1; i<=n; i++) cout << d[i];
  64.             dfs(j);
  65.         }
  66.     }
  67.     //cout << c+s-1;
  68.     /*for(int i=1; i<=m; i++){
  69.         for(int j=1; j<=m; j++){
  70.             cout << mas[i][j] << " ";
  71.         }
  72.         cout << "\n";
  73.     }*/
  74.     //for(int i=1; i<=m; i++)  cout << deg[i] << " ";
  75.     int s0=0;
  76.     for(int i=1; i<=m; i++){
  77.         int g=0;
  78.         for(int j=1; j<=m; j++){
  79.           g=g+mas[i][j];
  80.         }
  81.         if(g==0) s0++;
  82.     }
  83.  
  84.  
  85.     cout << s+c-p-s0;
  86. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top