Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- using namespace std;
- int n, m, nd = 0, ans = 0, g = 0;
- bool was[(int)1e5];
- int arr[(int)1e5];
- int mas[(int)1e5];
- vector <vector<int>> gr;
- void input(){
- int a, b;
- cin >> n >> m; // n - kolvo vershin, m - kolvo strok (reber)
- gr.resize(n+1);
- for(int i = 0; i < m; i++){
- cin >> a;
- cin >> b;
- gr[a].pb(b);
- gr[b].pb(a);
- }
- }
- void output(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int b = 0;
- cout << ans << endl;
- for(int i = 1; i <= ans; i++){
- cout << arr[i] << endl;
- for(int j = b; j < arr[i]+b; j++){
- cout << mas[j] << " ";
- }
- cout << endl;
- b += arr[i];
- }
- }
- void dfs(int v){
- int to;
- nd++;
- mas[g] = v;
- g++;
- was[v] = true;
- int sz = gr[v].size();
- for(int j = 0; j < sz; j++){
- to = gr[v][j];
- if(!was[to]){
- dfs(to);
- }
- }
- }
- void solve(){
- int x;
- for(int i = 1; i <= n; i++){
- if(!was[i]){
- dfs(i);
- arr[ans+1] = nd;
- ans++;
- }
- }
- arr[0] = 0;
- for(int i = ans; i > 0; i--){
- x = arr[i] - arr[i-1];
- arr[i] = x;
- }
- }
- int main(){
- freopen("matrix.in", "r", stdin);
- freopen("matrix.out", "w", stdout);
- input();
- solve();
- output();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement