Cod sursa(job #3337100)

Utilizator leonardthethirdSir Leonard The Third leonardthethird Data 26 ianuarie 2026 22:16:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,x,y,comp = 0;
vector<int> visited;
vector<vector<int>> adj;
vector<vector<int>> adjT;
vector<vector<int>> rez;
stack<int> st;

void dfs(int nod){
    visited[nod] = 1;
    for(auto& neigh: adj[nod]){
        if(visited[neigh] == 0){
            dfs(neigh);
        }
    }
    st.push(nod);
}

void dfsT(int nod){
    visited[nod] = 2;
    rez[comp].push_back(nod);
    for(auto& neigh: adjT[nod]){
        if(visited[neigh] == 1){
            dfsT(neigh);
        }
    }
}

int main(){
    f >> n >> m;
    adj.resize(n+1, vector<int>());
    adjT.resize(n+1, vector<int>());
    visited.resize(n+1, 0);
    for(int i=1; i<=m; i++){
        f >> x >> y;
        adj[x].push_back(y);
        adjT[y].push_back(x);
    }
    for(int i=1; i<=n; i++){
        if(visited[i] == 0){
            dfs(i);
        }
    }

    while(!st.empty()){
        int nod = st.top();
        st.pop();

        if(visited[nod] == 1){
            rez.push_back(vector<int>());
            dfsT(nod);
            comp++;
        }
    }
    g << comp << '\n';
    for(int i=0; i<comp; i++){
        for(auto& elem: rez[i]){
            g << elem << " ";
        }
        g << '\n';
    }


    return 0;
}