Cod sursa(job #2142123)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 24 februarie 2018 19:13:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector <int> edge[N];
vector <vector <int>> ans;
stack <int> s;
bool used[N];
bool in_s[N];
int tin[N], low[N];
int fr = 0;

void dfs(int x){
    fr++;
    tin[x] = fr;
    low[x] = fr;
    used[x] = true;
    in_s[x] = true;
    s.push(x);
    for(auto &it : edge[x]){
        if(used[it] == false){
            dfs(it);
            low[x] = min(low[x], low[it]);
        }else if(in_s[it] == true){
            low[x] = min(low[x], tin[it]);
        }
    }
    if(tin[x] == low[x]){
        vector <int> ax;
        int y;
        do{
            y = s.top();
            s.pop();
            in_s[y] = false;
            ax.emplace_back(y);
        }while(y != x);
        ans.emplace_back(ax);
    }
}

int main(){
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1;i <= m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        edge[x].push_back(y);
    }
    for(int i = 1;i <= n;i++){
        if(used[i] == false){
            dfs(i);
        }
    }
    printf("%d\n", ans.size());
    for(auto &vect : ans){
        for(auto &it : vect){
            printf("%d ", it);
        }
        printf("\n");
    }
    return 0;
}