Pagini recente » Cod sursa (job #1242236) | Profil StarGold2 | Cod sursa (job #2361498) | Cod sursa (job #1514940) | Cod sursa (job #2572866)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int MAX = 200005;
int n, m, nr = 0;
bool vizitat[MAX];
vector <int> muchii[MAX], invers[MAX], componente[MAX];
stack <int> stiva;
void citire() {
in >> n >> m;
int x, y;
for(int i = 1; i <= m; i++) {
in >> x >> y;
muchii[x].push_back(y);
invers[y].push_back(x);
}
}
void DFS(int nodStart) {
vizitat[nodStart] = true;
for(unsigned int i = 0; i < muchii[nodStart].size(); i++) {
int vecin = muchii[nodStart][i];
if(!vizitat[vecin])
DFS(vecin);
}
stiva.push(nodStart);
}
void DFS_T(int nodCurent) {
vizitat[nodCurent] = false;
componente[nr].push_back(nodCurent);
for(unsigned int i = 0; i < invers[nodCurent].size(); i++) {
int vecin = invers[nodCurent][i];
if(vizitat[vecin])
DFS_T(vecin);
}
}
void Solve() {
for(int i = 1; i <= n; i++)
if(!vizitat[i])
DFS(i);
while(!stiva.empty()) {
int nodCurent = stiva.top();
if(vizitat[nodCurent]) {
nr++;
DFS_T(nodCurent);
}
stiva.pop();
}
}
void afisare() {
out << nr << "\n";
for(int i = 1; i <= nr; i++) {
for(unsigned int j = 0; j < componente[i].size(); j++)
out << componente[i][j] << " ";
out << "\n";
}
}
int main() {
citire();
Solve();
afisare();
return 0;
}