Cod sursa(job #2928827)

Utilizator iulitaalpetriIulita Alpetri iulitaalpetri Data 23 octombrie 2022 22:35:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.01 kb
//#include <fstream>
//#include <iostream>
//#include <vector>
//#include <stack>
//
//using namespace std;
////Pentru a afla nr de componente tare conexe(pt oricare doua noduri i si j, exista nod de la i la j si de la j la i), voi folosi algoritmul lui kosaraju.
//int N,M, x, y;
//stack<int> stiva;
//vector<vector<int>> lista_adiacenta;
//vector<vector<int>> lista_transpus;
//vector<bool> vizitat_1;
//vector<bool> vizitat_2;
//int nr;
//vector<vector<int>> ctc;
//
//void dfs(int nod){
//    vizitat_1[nod]= true;
//    for(auto i: lista_adiacenta[nod]){
//        if(!vizitat_1[i]) dfs(i);
//    }
//
//    stiva.push(nod);
//}
//
//void dfs_transpus(int nod){
//    ctc[nr].push_back(nod);
//    vizitat_2[nod]= true;
//    for(auto i: lista_transpus[nod]){
//        if(!vizitat_2[i]) dfs_transpus(i);
//    }
//}
//
//
//int main(){
//    ifstream f("ctc.in");
//    ofstream g("ctc.out");
//    f>>N>>M;
//
//    lista_adiacenta.resize(N+1);
//    lista_transpus.resize(N+1);
//    vizitat_1.resize(N+1, false);
//    vizitat_2.resize(N+1, false);
//    ctc.resize(N+1);
//
////formam lista de adiacenta
//    for(int i=1; i<=M;i++){
//        f>>x>>y;
//        lista_adiacenta[x].push_back(y);
//        lista_transpus[y].push_back(x);
//    }
//    f.close();
//    dfs(1);
//    while(!stiva.empty()){
//        int a= stiva.top();
//        stiva.pop();
//        if(!vizitat_2[a]){nr++;
//            dfs_transpus(a);}
//    }
//
//    g<<nr<<endl;
//
//    for(int i=1; i<=nr; i++){
//        for(int j=0; j< ctc[i].size(); j++) g<<ctc[i][j]<<" ";
//        g<<endl;
//    }
//    return 0;
//}

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

// matricea de adiacenta a grafului
vector<vector<int>> m;

// matricea transpusa a grafului
vector<vector<int>> m_t;

// vector care determina nivelul unui nod
vector<int> n;

int nr_cc;
// vector unde este stocat rezultatul
vector<vector<int>> cc;

// stiva pentru evidenta nodurilor parcurse la DFS
vector<int> s;

void DFS(int x){
    for(auto e: m[x])
        if(n[e] == 0){
            n[e] = 1;
            DFS(e);
        }

    s.push_back(x);
}

void DFS_T(int x){
    cc[nr_cc].push_back(x);

    n[x] = 2;

    for(auto e: m_t[x])
        if(n[e] == 1)
            DFS_T(e);
}

int main(){

    int N,M,a,b;

    // citire
    ifstream f("ctc.in");

    f>>N>>M;

    m.resize(N + 1);
    m_t.resize(N + 1);
    n.resize(N + 1, 0);
    cc.resize(N + 1);

    for(int i = 0; i < M; i++){
        f>>a>>b;

        m[a].push_back(b);
        m_t[b].push_back(a);
    }

    f.close();

    for(int i = 1; i <= N; i++){
        if(n[i] == 0){
            n[i] = 1;
            DFS(i);
        }
    }

    while(!s.empty()){
        a = s.back();
        s.pop_back();

        if(n[a] == 1){
            nr_cc++;
            DFS_T(a);
        }
    }

    ofstream g("ctc.out");

    g<<nr_cc<<endl;

    for(int i = 1; i <= nr_cc; i++){
        for(int j = 0; j < cc[i].size(); j++)
            g<<cc[i][j]<<' ';
        g<<endl;
    }

    g.close();
    return 0;
}