Pagini recente » Cod sursa (job #151825) | Clasament sanki | Cod sursa (job #155731) | Cod sursa (job #292749) | Cod sursa (job #2488035)
#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
//using namespace std;
#define NMAX 100005
//liste de adiacenta si transpusa
std::vector<int> v[NMAX], vT[NMAX];
//vec comp conexe
std::vector<std::vector<int>> vecCon;
std::vector<int> H;
//vector vizita
int uz[NMAX];
//nr de noduri
int n;
void Citire(void);
void Afisare(void);
void DFS(int);
void DFST(int);
int main()
{
Citire();
for (int i = 1; i <= n; i++)
if (!uz[i]) DFS(i);
memset(uz, 0, sizeof(uz));
for (int i = H.size()-1; i>= 0; i--)
if (!uz[H[i]])
{
vecCon.push_back(std::vector<int>());
DFST(H[i]);
}
Afisare();
return 0;
}
void Citire()
{
std::fstream fin("ctc.in");
int m;
int a, b;
fin >> n >> m;
//aloc memorie pentru fiecare varf
for (int i = 1; i <= m; i++)
{
fin >> a >> b;
v[a].push_back(b);
vT[b].push_back(a);
}
}
void Afisare()
{
std::ofstream fout("ctc.out");
fout << vecCon.size() << std::endl;
for (std::vector<std::vector<int>>::iterator it = vecCon.begin(); it != vecCon.end(); ++it)
{
for (std::vector<int>::iterator it2 = it->begin(); it2 != it->end(); ++it2)
fout << *it2 << ' ';
fout << std::endl;
}
fout.close();
}
void DFS(int nod)
{
uz[nod] = 1;
for (std::vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
{
if (!uz[*it]) DFS(*it);
}
H.push_back(nod);
}
void DFST(int nod)
{
uz[nod] = 1;
for (std::vector<int>::iterator it = vT[nod].begin(); it != vT[nod].end(); ++it)
{
if (!uz[*it]) DFST(*it);
}
vecCon.back().push_back(nod);
}