Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3.  
  4. using namespace std;
  5.  
  6. int n, m, nd = 0, ans = 0, g = 0;
  7. bool was[(int)1e5];
  8. int arr[(int)1e5];
  9. int mas[(int)1e5];
  10.  
  11. vector <vector<int>> gr;
  12.  
  13. void input(){
  14.     int a, b;
  15.     cin >> n >> m; // n - kolvo vershin, m - kolvo strok (reber)
  16.     gr.resize(n+1);
  17.     for(int i = 0; i < m; i++){
  18.         cin >> a;
  19.         cin >> b;
  20.         gr[a].pb(b);
  21.         gr[b].pb(a);
  22.     }
  23. }
  24.  
  25. void output(){
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(NULL);
  28.     int b = 0;
  29.     cout << ans << endl;
  30.     for(int i = 1; i <= ans; i++){
  31.         cout << arr[i]  << endl;
  32.         for(int j = b; j < arr[i]+b; j++){
  33.             cout << mas[j] << " ";
  34.         }
  35.         cout << endl;
  36.         b += arr[i];
  37.     }
  38. }
  39.  
  40. void dfs(int v){
  41.     int to;
  42.     nd++;
  43.     mas[g] = v;
  44.     g++;
  45.     was[v] = true;
  46.     int sz = gr[v].size();
  47.     for(int j = 0; j < sz; j++){
  48.         to = gr[v][j];
  49.         if(!was[to]){
  50.             dfs(to);
  51.         }
  52.     }  
  53. }
  54.  
  55. void solve(){
  56.     int x;
  57.     for(int i = 1; i <= n; i++){
  58.         if(!was[i]){
  59.             dfs(i);
  60.             arr[ans+1] = nd;
  61.             ans++;
  62.         }
  63.     }
  64.     arr[0] = 0;
  65.     for(int i = ans; i > 0; i--){
  66.         x = arr[i] - arr[i-1];
  67.         arr[i] = x;
  68.     }
  69. }
  70.  
  71. int main(){
  72.     freopen("matrix.in", "r", stdin);
  73.     freopen("matrix.out", "w", stdout);
  74.     input();  
  75.     solve();
  76.     output();
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement