Pagini recente » Cod sursa (job #1881677) | Cod sursa (job #1161274) | Cod sursa (job #2367458) | Cod sursa (job #1261594) | Cod sursa (job #2863509)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define NMax 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int N, VIZ[NMax], comp_conexe;
vector <int> Graf[NMax], Graf_t[NMax], sol[NMax];
stack <int> Stiva;
void DFS(int nod)
{
VIZ[nod] = 1;
for(unsigned int i = 0; i < Graf[nod].size(); ++ i)
if(VIZ[Graf[nod][i]] == 0)
DFS(Graf[nod][i]);
Stiva.push(nod);
}
void DFS_2(int nod_2)
{
VIZ[nod_2] = 2;
sol[comp_conexe].push_back(nod_2);
for(unsigned int i = 0; i < Graf_t[nod_2].size(); ++ i)
if(VIZ[Graf_t[nod_2][i]] == 1)
DFS_2(Graf_t[nod_2][i]);
}
void Kosaraju()
{
for(int i = 1; i <= N; ++ i)
if(VIZ[i] == 0)
DFS(i);
while( !Stiva.empty() )
{
int nodCurent = Stiva.top();
Stiva.pop();
if(VIZ[nodCurent] == 1)
{
comp_conexe ++;
DFS_2(nodCurent);
}
}
}
int main()
{
int M, x, y;
fin >> N >> M;
for(int i = 1; i <= M; ++ i)
{
fin >> x >> y;
Graf[x].push_back(y);
Graf_t[y].push_back(x);
}
fin.close();
Kosaraju();
fout << comp_conexe << '\n';
for(int i = 1; i <= comp_conexe; ++ i, fout << '\n')
for(unsigned int j = 0; j < sol[i].size(); ++ j)
fout << sol[i][j] << ' ';
fout.close();
return 0;
}