Pagini recente » Cod sursa (job #857108) | Cod sursa (job #2139380) | Clasament preoni5a | Cod sursa (job #938107) | Cod sursa (job #2423807)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NLIM 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int viz[NLIM];
vector<int> Muchii[NLIM], MuchiiT[NLIM], Conex[NLIM];
stack<int> Topo;
void citire(int &n, int &m) {
f >> n >> m;
for(int i=1; i<=m; i++) {
int s, d;
f >> s >> d;
Muchii[s].push_back(d);
MuchiiT[d].push_back(s);
}
}
void DFS(int nod, bool transpose = false, int conex = -1) {
viz[nod] = transpose ? 2 : 1;
if(transpose) Conex[conex].push_back(nod);
for(int i=0; i<(transpose ? Muchii : MuchiiT)[nod].size(); i++) {
int vecin = (transpose ? Muchii : MuchiiT)[nod][i];
if(!viz[vecin] && ! transpose)
DFS(vecin);
else if(viz[vecin] == 1 && transpose) {
DFS(vecin, transpose, conex);
}
}
if(!transpose) Topo.push(nod);
}
int Kosoraju(int n) {
int conex = 0;
for(int i=1; i<=n; i++)
if(!viz[i])
DFS(i);
while(!Topo.empty()) {
int top = Topo.top();
Topo.pop();
if(viz[top] == 1) {
conex++;
DFS(top, true, conex);
}
}
return conex;
}
int main() {
int n, m, ctc;
citire(n, m);
ctc = Kosoraju(n);
g << ctc << '\n';
for(int i=1; i<=ctc; i++) {
for (int j = 0; j < Conex[i].size(); j++)
g << Conex[i][j] << ' ';
g << '\n';
}
return 0;
}