Cod sursa(job #2867581)

Utilizator VanillaSoltan Marian Vanilla Data 10 martie 2022 13:58:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 100001;
vector <int> ad [maxn];
vector <int> adrev [maxn];
vector <int> order;
bitset <maxn> vis;
vector <vector <int> > rs;
ifstream in ("ctc.in");
ofstream out ("ctc.out");

void topo (int u) {
    vis[u] = 1;
    for (auto v: ad[u]){
        if (!vis[v]) topo(v);
    }
    order.push_back(u);
}

void dfs (int u, vector <int> &arr) {
    arr.push_back(u);
    vis[u] = 1;
    for (int v: adrev[u]){
        if (!vis[v]) dfs(v, arr);
    }
}


int main() {
    int n, m;
    in >> n >> m;
    while (m--) {
        int x,y;
        in >> x >> y;
        ad[x].push_back(y);
        adrev[y].push_back(x);
    }
    for (int i = 1; i <= n; i++){
        if (!vis[i]) {
            topo(i);
        }
    }
    for (int i = 1; i <= n; i++) vis[i] = 0;
    reverse(order.begin(), order.end());
    for (int node: order){
        if (!vis[node]){
            rs.push_back(vector<int> ());
            dfs(node, rs[rs.size() - 1]);
        }
    }    
    out << rs.size() << "\n";
    for (auto i: rs){
        for (auto j: i){
            out << j << " ";
        }
        out << "\n";
    }

}