Pagini recente » Cod sursa (job #400943) | Cod sursa (job #188317) | Cod sursa (job #2013001) | Cod sursa (job #2195320) | Cod sursa (job #2908044)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m; // numarul de noduri, respectiv de muchii
vector<vector<int>>vecini; // liste de vecini
vector<bool>vizitat; // marcarea varfurilor vizitate in parcurgere
vector<vector<int>>veciniTranspus; // liste de vecini pentru graful transpus
stack<int>timpiFinalizare; // stiva in care stochez nodurile in ordinea desc a timpilor de finalizare
vector<vector<int>>componenteTareConexe; // stochez pentru fiecare componenta tare conexa nodurile care o alcatuiesc
int nrComponenteTareConexe;
void dfs(int u){
vizitat[u] = 1;
for(int i = 0; i < vecini[u].size(); i++)
if(!vizitat[vecini[u][i]])
dfs(vecini[u][i]);
timpiFinalizare.push(u);
}
void dfsTranspus(int u){
componenteTareConexe[nrComponenteTareConexe].push_back(u);
vizitat[u] = 1;
for(int i = 0; i < veciniTranspus[u].size(); i++)
if(!vizitat[veciniTranspus[u][i]])
dfsTranspus(veciniTranspus[u][i]);
}
int main()
{
f >> n >> m;
vecini.resize(n + 1);
vizitat.resize(n + 1, 0);
veciniTranspus.resize(n + 1);
componenteTareConexe.resize(n + 1);
for(int i = 0; i < m; i++){
int u, v;
f >> u >> v;
vecini[u].push_back(v);
veciniTranspus[v].push_back(u);
}
// prima parcurgere o facem in graful normal
// pentru a determina timpii de finalizare
for(int i = 1; i <= n; i++)
if(!vizitat[i])
dfs(i);
for(int i = 0; i <= n; i++)
vizitat[i] = 0;
// a doua parcurgere o sa fie facuta in graful transpus
// si de asemenea o sa tinem cont de timpii de finalizare determinati mai sus
while(!timpiFinalizare.empty()){
int u = timpiFinalizare.top();
timpiFinalizare.pop();
if(!vizitat[u]){
nrComponenteTareConexe++;
dfsTranspus(u);
}
}
g << nrComponenteTareConexe << "\n";
for(int i = 1; i <= nrComponenteTareConexe; i++){
for(int j = 0; j < componenteTareConexe[i].size(); j++)
g << componenteTareConexe[i][j] << " ";
g << "\n";
}
return 0;
}