Pagini recente » Cod sursa (job #1237552) | Cod sursa (job #2419585) | Cod sursa (job #1414015) | Cod sursa (job #26539) | Cod sursa (job #2929513)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
vector<vector<int>> graf;
vector<vector<int>> grafTranspus;
vector<bool> vizitat;
stack<int> stiva;
vector<vector<int>> lista_ctc;
int N, M;
void citireGraf(){
ifstream fin("ctc.in");
fin >> N >> M;
graf = vector<vector<int>>(N+1);
vizitat = vector<bool>(N+1);
for(int i = 0; i < M; i++){
int nod_1, nod_2;
fin >> nod_1 >> nod_2;
graf[nod_1].push_back(nod_2);
}
}
void DFS(vector<vector<int>> g, int nod_start, vector<int> &ctc, bool transpus = false){
if(transpus)
ctc.push_back(nod_start);
vizitat[nod_start] = true;
for(auto nod_vecin: g[nod_start])
if(!vizitat[nod_vecin])
DFS(g, nod_vecin, ctc, transpus);
if(!transpus)
stiva.push(nod_start);
}
int main() {
citireGraf();
// Pasul 0 - Construim grafTranspus
grafTranspus = vector<vector<int>>(N+1);
for(int i = 1; i <= N; i++)
for(auto nod_vecin: graf[i])
grafTranspus[nod_vecin].push_back(i);
// Pasul 1 - Parcurgem DFS graf si introducem intr-o stiva fiecare varf la momentul in care este finalizat
vector<int> temp;
for(int i = 1; i <= N; i++)
if(!vizitat[i])
DFS(graf, i, temp, false);
// Pasul 2 - Parcurgem DFS grafTranspus considerand varfurile in ordinea in care sunt extrase din S
vizitat = vector<bool> (N+1);
while(!stiva.empty()){
int nod_curent = stiva.top();
stiva.pop();
if(!vizitat[nod_curent]) {
vector<int> ctc = vector<int>(0);
DFS(grafTranspus, nod_curent, ctc, true);
lista_ctc.push_back(ctc);
}
}
ofstream fout("ctc.out");
fout << lista_ctc.size() << '\n';
for(const auto& ctc: lista_ctc) {
for (auto nod: ctc)
fout << nod << ' ';
fout << '\n';
}
fout.close();
return 0;
}