Cod sursa(job #3252941)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 31 octombrie 2024 16:02:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>st;
vector<bool>viz;
vector<vector<int>>ctc;
//void dfs2(int node, vector<vector<int>>&edges, vector<int>&add_to) {
//    viz[node]=1;
//    for (auto newnode:edges[node]) {
//        int newnode=edges[node][i];
//        if (!viz[newnode]) {
//            dfs(noewnode, edges);
//        }
//    }
//    add_to.push_back(node);
//}
void dfs(int node, vector<vector<int>>&edges, vector<int>&add_to) {
    viz[node]=1;
    for (auto it:edges[node]) {
        if (viz[it]==0) dfs(it, edges, add_to);
    }
    add_to.push_back(node);
}
void Solve() {
    int n, m; fin>>n>>m;
    vector<vector<int>>edges(n);
    vector<vector<int>>rev_edges(n);
    for (int i=0; i<m; i++) {
        int a, b;
        fin>>a>>b;
        a--;
        b--;
        edges[a].push_back(b);
        rev_edges[b].push_back(a);
    }
    viz.resize(n);
    vector<int>st;
    for (int node=0; node<n; node++) {
        if (!viz[node]) dfs(node, edges, st);
    }
    viz.clear();
    viz.resize(n);
    vector<vector<int>>ctc;
    for (int i=st.size()-1; i>=0; i--) {
        if (viz[st[i]]==0) {
            ctc.push_back(vector<int>());
            dfs(st[i], rev_edges, ctc.back());
        }
    }
    fout<<ctc.size()<<'\n';
    for (auto comp:ctc) {
        for (auto node:comp) {
            fout<<node+1<<' ';
        }
        fout<<'\n';
    }
}
int main()
{
    Solve();
    return 0;
}