Mai intai trebuie sa te autentifici.
Cod sursa(job #2338547)
Utilizator | Data | 7 februarie 2019 16:39:02 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.49 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define NMax 100005
vector < int > G[NMax], GT[NMax], result[NMax];
stack < int > S;
int N, M, NrCTC;
int beenThere[NMax];
void Read(){
fin >> N >> M;
for(int i = 1; i <= M; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFS(int Nod){
beenThere[Nod] = 1;
// Zona 1
for(unsigned int i = 0; i < G[Nod].size(); i++){
// Zona 2
int Vecin = G[Nod][i];
if(!beenThere[Vecin])
DFS(Vecin);
//Zona 3
}
S.push(Nod);
//Zona 4
}
void DFS_T(int Nod){
beenThere[Nod] = 2;
result[NrCTC].push_back(Nod);
for(unsigned int i = 0; i < GT[Nod].size(); i++){
int Vecin = GT[Nod][i];
if(beenThere[Vecin] == 1)
DFS_T(Vecin);
}
}
void Solve(){
for(int i = 1; i <= N; i++)
if(!beenThere[i])
DFS(i);
while(!S.empty()){
int Nod = S.top();
//cout << Nod << " ";
if(beenThere[Nod] == 1){
NrCTC++;
DFS_T(Nod);
}
S.pop();
}
}
void Print(){
fout << NrCTC << "\n";
for(int i = 1; i <= NrCTC; i++){
for(unsigned int j = 0; j < result[i].size(); j++)
fout << result[i][j] << " ";
fout << "\n";
}
}
int main() {
Read();
Solve();
Print();
return 0;
}