Cod sursa(job #3307449)

Utilizator Zeno1789Zeno Ciuca Zeno1789 Data 20 august 2025 19:52:53
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

ifstream cin ("ctc.in");
ofstream cout ("ctc.out");

vector <int> G[100002];
vector <int> Gt[100002];
vector <int> st;
vector <vector<int>> ctc;
char vizitat[100002];
int comp[100002];

void sort_top(int node) {
    vizitat[node]=1;
    for (int x:G[node]) {
        if (!vizitat[x]) sort_top(x);
    }
    st.push_back(node);
    return;
}

void dfs(int node,vector <int> *G,int curr) {
    comp[node]=curr;
    ctc[curr-1].push_back(node);
    for (int x:G[node]) {
        if (comp[x]==0) dfs(x,G,curr);
    }
}

int main() {
    int n,m,x,y;
    cin>>n>>m;
    for (int i=1; i<=m; i++) {
        cin>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for (int i=1; i<=n; i++){
        if (!vizitat[i]) sort_top(i);
    }
    reverse(st.begin(),st.end());
    memset(vizitat,0,sizeof(vizitat));
    for (int i:st) {
        if (comp[i]==0) {
            ctc.push_back({});
            dfs(i,Gt,ctc.size());
        }
    }
    cout<<ctc.size()<<'\n';
    for (vector<int> comp:ctc){
        for (int node:comp) {
            cout<<node<<' ';
        }
        cout<<'\n';
    }
}