Cod sursa(job #2579614)

Utilizator TveinDenisDenis Tvein TveinDenis Data 12 martie 2020 17:45:07
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using std::cout;
using std::endl;
using std::cin;
using std::vector;
using std::queue;
using std::stack;
using std::fstream;
using std::ios;
using std::sort;

fstream file1("ctc.in", ios::in);
fstream file2("ctc.out", ios::out);

int nr_noduri, nr_muchii, count;
vector<int> vecini[100005], vecini_inv[100005], sol[100005];
vector<bool> vizitat(100005), vizitat_inv(100005);
stack<int> stiva;

void form_vecini();
void f();
void dfs(int start);
void dfs_t(int start);

int main(int argc, char** argv) {
    
    file1 >> nr_noduri >> nr_muchii;
    form_vecini();

    f();
    file2 << count << endl;
    for (int i{ 0 }; i < count; i++) {
        for (int j{ 0 }; j < sol[i].size(); j++) {
            file2 << sol[i][j] << ' ';
        }
        file2 << endl;
    }

    file1.close();
    file2.close();
    return 0;
}

void f() {
    for (int i{ 1 }; i <= nr_noduri; i++) {
        if (!vizitat[i]) {
            dfs(i);
        }
    }
    while (!stiva.empty()) {
        int nod = stiva.top();
        if (!vizitat_inv[nod]) {
            dfs_t(nod);
            count++;
        }
        stiva.pop();
    }
}

void dfs_t(int start) {
    vizitat_inv[start] = true;
    for (auto it = vecini_inv[start].begin(); it != vecini_inv[start].end(); it++) {
        if (!vizitat_inv[*it]) {
            vizitat_inv[*it] = true;
            dfs_t(*it);
        }
    }
    sol[count].push_back(start);
}

void dfs(int start) {
    vizitat[start] = true;
    for (auto it = vecini[start].begin(); it != vecini[start].end(); it++) {
        if (!vizitat[*it]) {
            vizitat[*it] = true;
            dfs(*it);
        }
    }
    stiva.push(start);
}

void form_vecini() {
    int i, j;
    while (file1 >> i >> j) {
        vecini[i].push_back(j);
        vecini_inv[j].push_back(i);
    }
}