Pagini recente » Cod sursa (job #1247506) | Cod sursa (job #1254281) | Cod sursa (job #60839) | Cod sursa (job #1255959) | Cod sursa (job #2034071)
#include <iostream>
#include <fstream>
#define DMAX 100001
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
typedef struct elem{
int val;
elem * urm;
}VECIN;
int n, m;
VECIN * nodSpre[DMAX], *nodIn[DMAX];
bool validare1[DMAX], validare2[DMAX];
int st1[DMAX];
int numar;
void citire(){
in >> n>> m;
for(int i = 1; i<= m; i++){
int x, y;
in >> x >> y;
VECIN *deAdaugat = new VECIN;
deAdaugat -> val = y;
deAdaugat -> urm = nodSpre[x];
nodSpre[x] = deAdaugat;
VECIN * deAdaugat2 = new VECIN;
deAdaugat2 -> val = x;
deAdaugat2 -> urm = nodIn[y];
nodIn[y] = deAdaugat2;
}
}
void parcurgereDF(int el,VECIN *nod[], bool viz[]){//ok
int st[DMAX], varf;
bool ok = false;
st[1] = el;
viz[el] = true;
varf = 1;
while (varf != 0){
VECIN * parcurg ;
parcurg = nod[st[varf]];
ok = false;
while(parcurg != NULL){
if(viz[parcurg -> val] == false){
ok = true;
st[++ varf] = parcurg -> val;
viz[parcurg -> val] = true;
break;
}else{
parcurg = parcurg -> urm;
}
}
if(ok == false && varf != 0){
st1[++st1[0]] = st[varf];
varf --;
}
}
}
void parcurgereDFFinala(int el,VECIN *nod[], bool viz[],int nr){//ok
int st[DMAX], varf;
bool ok ;
st[1] = el;
viz[el] = true;
varf = 1;
while (varf != 0){
VECIN * parcurg;
parcurg = nod[st[varf]];
ok = false;
while(parcurg != NULL){
if(viz[parcurg -> val] == false){
ok = true;
st[++ varf] = parcurg -> val;
viz[parcurg -> val] = true;
break;
}else{
parcurg = parcurg -> urm;
}
}
if(ok == false && varf != 0) {
VECIN *deAdaugat = new VECIN;
deAdaugat -> val = st[varf];
deAdaugat -> urm = nodSpre[nr];
nodSpre[nr] = deAdaugat;
varf --;
}
}
}
void construireStivaDf(){
for(int i = 1; i<=n ; i++){
if(validare1[i] == false){
parcurgereDF(i, nodSpre, validare1);
}
}
}
void parcurgereInversa(){
while(st1[0] != 0){
if(validare2[st1[st1[0]]] == false){
nodSpre[++numar] = NULL;
parcurgereDFFinala(st1[st1[0]], nodIn, validare2, numar);
}
st1[0]--;
}
}
void afisare(){
out << numar <<'\n';
for(int i = 1; i<= numar; i++){
while (nodSpre[i] != NULL){
out << nodSpre [i]-> val << ' ';
nodSpre[i] = nodSpre[i]->urm;
}
out << '\n';
}
}
int main() {
citire();
construireStivaDf();
parcurgereInversa();
afisare();
return 0;
}