SHARE
TWEET

Untitled

a guest Feb 21st, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <stdio.h>
  5. using namespace std;
  6.  
  7. bool used[200000];
  8. int answ[200000];
  9. int kolkomp = 0;
  10. vector<int> g[300000];
  11. int n;
  12. vector<int> comp;
  13.  
  14. void dfs (int v)
  15. {
  16.     used[v] = true;
  17.     comp.push_back (v);
  18.     for (size_t i=0; i<g[v].size(); ++i)
  19.     {
  20.         int to = g[v][i];
  21.         if (! used[to])
  22.             dfs (to);
  23.     }
  24. }
  25.  
  26. void find_comps()
  27. {
  28.     for (int i=0; i<n; ++i)
  29.         used[i] = false;
  30.     for (int i=0; i<n; ++i)
  31.         if (! used[i])
  32.         {
  33.             comp.clear();
  34.             dfs (i);
  35.             kolkomp++;
  36.             //cout << "Component:";
  37.             for (size_t j=0; j<comp.size(); ++j)
  38.             {
  39.                 //kolkomp++;
  40.                 answ[comp[j]] = kolkomp;
  41.             }//cout << ' ' << comp[j] + 1;
  42.             //cout << endl;
  43.         }
  44. }
  45.  
  46. int main()
  47. {
  48.     freopen("components.in","r",stdin);
  49.     freopen("components.out","w",stdout);
  50.     int m;
  51.     scanf("%d %d\n", &n, &m);
  52.     for(int i = 0; i < n; i++)
  53.         used[i] = 0;
  54.     for(int i = 0; i < m; i++)
  55.     {
  56.         int a, b;
  57.         scanf("%d %d\n", &a, &b);
  58.         if(a<=b)
  59.             g[a - 1].push_back( b - 1);
  60.         else
  61.             g[b - 1].push_back( a - 1);
  62.     }
  63.  
  64.     for(int i = 0; i < 200000; i++)
  65.         answ[i]=0;
  66.     find_comps();
  67.     cout<<kolkomp<<'\n';
  68.     for(int i = 0; i < 200000; i++)
  69.     {
  70.         if(answ[i]==0)
  71.             break;
  72.         cout<<answ[i]<<" ";
  73.     }
  74.     return 0;
  75. }
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