Pagini recente » Istoria paginii utilizator/angelbejinaru | Istoria paginii runda/kk-kkk | Cod sursa (job #612643) | Cod sursa (job #2386735) | Cod sursa (job #951090)
Cod sursa(job #951090)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <string>
#include <stack>
using namespace std;
fstream in, out;
vector<int> *graf, *grafT, *compCTC;
stack<int> stiva;
bitset<100001> vizitat;
int nrNoduri, nrMuchii, nrCTC;
void dfsGT(int);
void dfs(int);
void start();
int main()
{
in.open("ctc.in", ios::in);
out.open("ctc.out", ios::out);
int aux1, aux2;
in >> nrNoduri >> nrMuchii;
graf = new vector<int> [nrNoduri + 1];
grafT = new vector<int> [nrNoduri + 1];
compCTC = new vector<int> [nrNoduri + 1];
for (int i = 1; i <= nrMuchii; i++){
in >> aux1 >> aux2;
graf[aux1].push_back(aux2);
grafT[aux2].push_back(aux1);
}
start();
out << nrCTC << endl;
for (int i = 1; i <= nrCTC; i++){
for (int j = 0; j < compCTC[i].size(); j++){
out << compCTC[i][j] << " ";
}
out << endl;
}
return 0;
}
void start(){
//fill (vizitat, vizitat + 100001, 0);
vizitat.reset();
for (int i = 1; i <= nrNoduri; ++i){
if (!vizitat[i]){
dfs(i);
stiva.push(i);
}
}
//fill (vizitat, vizitat + 100001, 0);
vizitat.reset();
while (!stiva.empty()){
int x = stiva.top();
nrCTC++;
dfsGT(x);
int aux = stiva.top();
compCTC[nrCTC].push_back(aux);
stiva.pop();
}
}
void dfsGT(int x){
vizitat[x] = 1;
for (int i = 0; i < grafT[x].size(); i++){
int y = grafT[x][i];
if (!vizitat[y]){
dfsGT(y);
int aux = stiva.top();
compCTC[nrCTC].push_back(aux);
stiva.pop();
}
}
}
void dfs(int x){
vizitat[x] = 1;
for (int i = 0; i < graf[x].size(); i++){
int y;
y = graf[x][i];
if (!vizitat[y]){
dfs(y);
stiva.push(y);
}
}
}