Pagini recente » Cod sursa (job #2591039) | Cod sursa (job #2259065) | Cod sursa (job #1338266) | Cod sursa (job #2356834) | Cod sursa (job #2107492)
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int MAX = 100005;
bool beenThere[MAX];
vector < int > myVector1[MAX];
vector < int > myVector2[MAX];
vector < int > newVector[MAX];
int Timp[MAX];
int Count;
int Retin;
int Answer;
int N,M;
void Read()
{
in >> N >> M;
int x,y;
while ( in >> x >> y)
{
myVector1[x].push_back(y);
myVector2[y].push_back(x);
}
}
void DFS(int Nod)
{
beenThere[Nod] = true;
for ( size_t i = 0 ; i < myVector1[Nod].size() ; ++i)
{
int Vecin = myVector1[Nod][i];
if(beenThere[Vecin] == false)
{
beenThere[Vecin] = true;
DFS(Vecin);
}
}
Timp[++Count] = Nod;
}
void DFStranspus(int Nod)
{
beenThere[Nod] = true;
newVector[Answer].push_back(Nod);
for( size_t i = 0; i < myVector2[Nod].size() ; ++i)
{
int Vecin = myVector2[Nod][i];
if(beenThere[Vecin] == false)
{
DFStranspus(Vecin);
}
}
}
void Rezolv()
{
for (int i = 1; i <= N ; ++i)
if(beenThere[i] == false)
DFS(i);
for ( int i = 1; i <= N ; ++i)
beenThere[i] = false;
for ( int i = N ; i >= 1 ; --i)
{
if(beenThere[Timp[i]] == false)
{ Answer++;
DFStranspus(Timp[i]);
}
}
out << Answer << "\n";
for ( int i = 1; i <= Answer; ++i)
{
for (size_t j = 0 ; j< newVector[i].size() ; ++j)
out <<newVector[i][j] <<" ";
out << "\n";
}
}
int main()
{
Read();
Rezolv();
return 0;
}