Cod sursa(job #3040240)

Utilizator TODEToderita Mihai TODE Data 29 martie 2023 16:29:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 1e5;
vector<int> v[N + 1] , v1[N + 1] , ctc[N + 1]; // v -> succesori , v1 -> pred
stack<int> s;
int sort_t[N + 1] , visited[N + 1] , nr_ord_c[N + 1] , n , m , nr;
void dfs(int i){
    visited[i] = true;
    for(int y = 0 ; y < v[i].size() ; y++){
        int val = v[i][y];
        if(!visited[val]){
            dfs(val);
        }
    }
    s.push(i);
}
void dfs_invers(int i , int nr_ord){
    nr_ord_c[i] = nr_ord;
    for(int y = 0 ; y < v1[i].size() ; y++){
        int val = v1[i][y];
        if(!nr_ord_c[val]){
            dfs_invers(val , nr_ord);
        }
    }
}
int main(){
    in >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        int x , y;
        in >> x >> y;
        v[x].push_back(y);
        v1[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; i++){
        if(!visited[i]){
            dfs(i);
        }
    }
    while(!s.empty()){
        int x = s.top();
        s.pop();
        if(nr_ord_c[x] == 0){
            dfs_invers(x , ++nr);
        }
    }
    int maxi = -1;
    for(int i = 1 ; i <= n ; i++){
        maxi = max(maxi , nr_ord_c[i]);
        ctc[nr_ord_c[i]].push_back(i);
    }
    out << maxi << '\n';
    for(int i = 1 ; i <= maxi ; i++){
        for(int y = 0 ; y < ctc[i].size() ; ++y){
            out << ctc[i][y] << ' ';
        }
        out << '\n';
    }
}