Cod sursa(job #3323934)

Utilizator dariabulacuBulacu Daria dariabulacu Data 20 noiembrie 2025 15:00:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

// stack <int> s;

// void dfs(vector<vector<int>> &adiacenta, int startNode, vector<int>& viz, stack<int> &s){
//     viz[startNode]=1;
//     for (auto x : adiacenta[startNode])
//         if (viz[x]==0)
//         dfs(adiacenta, x, viz, s);
//     s.push(startNode);
// }

// void dfs_t (vector<vector<int>> &adiacenta_t, int startNode, vector<int> &viz){
//     viz[startNode] = 1; 
//     for (auto x: adiacenta_t[startNode])
//         if (viz[x]==0)
//             dfs_t(adiacenta_t, x, viz);
// }
// int main (){
//     int nrNoduri, i, j, nrComponente = 0;
//     cin>>nrNoduri;
//     vector<vector<int>> adiacenta(nrNoduri+1);
//     vector<vector<int>> adiacenta_t(nrNoduri+1);
//     vector<int>viz(nrNoduri+1,0);

//     while(cin>>i>>j){
//         adiacenta[i].push_back(j);
//         adiacenta_t[j].push_back(i);
//     }
//     for (i = 1; i<= nrNoduri; i++)
//         if (viz[i]==0)
//             dfs(adiacenta,i,viz,s);
//     viz.assign(nrNoduri+1, 0);
//     while (!s.empty()){
//         int curr = s.top();
//         cout<<curr<<" ";
//         s.pop();
//         if (viz[curr] == 0){
//             nrComponente ++ ;
//             dfs_t(adiacenta_t,curr,viz);
//         }
//     }
//     cout<<nrComponente;
// }

stack<int> s;

void dfs(vector<vector<int>> &adiacenta,int startNode, vector<int> &viz){
    viz[startNode]=1;
    for (auto x: adiacenta[startNode])
        if (viz[x]==0)
        dfs(adiacenta,x,viz);
    s.push(startNode);
}

void dfs_t(vector<vector<int>> &adiacenta, int startNode, vector<int>&viz, vector<int>&conex){
    viz[startNode]=1;
    for (auto x : adiacenta[startNode])
        if(viz[x]==0)
        {conex.push_back(x);
        dfs_t(adiacenta,x,viz,conex);}
}

int main(){
    int nrNoduri, nrMuchii, i ,j, cc = 0 ;
    cin>>nrNoduri>>nrMuchii;
    vector<vector<int>> adiac(nrNoduri+1);
    vector<vector<int>> adiac_T(nrNoduri+1);
    vector<vector<int>>conex(nrNoduri+1);
    vector<int>viz(nrNoduri+1,0);
    while(nrMuchii){
        cin>>i>>j;
        adiac[i].push_back(j);
        adiac_T[j].push_back(i);
        nrMuchii--;
    }
    for (i=1; i<=nrNoduri; i++){
        if (viz[i]==0)
        dfs(adiac,i,viz);
    }
    viz.assign(nrNoduri+1,0);
    while(!s.empty()){
        int curr = s.top();
        s.pop();
        if (viz[curr]==0){
            cc++;
            conex[cc].push_back(curr);
            dfs_t(adiac_T, curr, viz,conex[cc]);
        }
    }
    cout<<cc<<endl;
    for (i = 1; i<=cc; i++){
        for (j=0; j<conex[i].size(); j++)
        cout<<conex[i][j]<<" ";
    cout<<endl;
    }

}