Pagini recente » Cod sursa (job #573344) | Cod sursa (job #1948731) | Cod sursa (job #3193890) | Cod sursa (job #2968762) | Cod sursa (job #1317809)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define Max_Size 100002
using namespace std;
const char iname[] = "ctc.in";
const char oname[] = "ctc.out";
int N, M, Count;
bool Viz[Max_Size];
vector < int > V[Max_Size], W[Max_Size], Sol[Max_Size];
stack < int > my_Stack;
inline void Read_Data()
{
ifstream in( iname );
in >> N >> M;
for(int x, y, i = 1; i <= M; ++i) {
in >> x >> y;
V[x].push_back(y);
W[y].push_back(x);
}
}
void DFS1(int nod)
{
Viz[nod] = 1;
for(vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); ++it)
if(!Viz[ *it ]) DFS1( *it );
my_Stack.push(nod);
}
void DFS2(int nod)
{
Viz[nod] = 1, Sol[Count].push_back( nod );
for(vector < int > :: iterator it = W[nod].begin(); it != W[nod].end(); ++it)
if(!Viz[ *it ]) DFS2( *it );
}
int main()
{
Read_Data();
for(int i = 1; i <= N; ++i)
if(!Viz[i]) DFS1( i );
memset(Viz, 0, sizeof( Viz ));
for(; !my_Stack.empty(); my_Stack.pop())
if(!Viz[ my_Stack.top() ]) ++Count, DFS2( my_Stack.top());
ofstream out( oname );
out << Count << '\n';
for(int i = 1; i <= Count; ++i) {
for(int j = 0; j < Sol[i].size(); ++j) out << Sol[i][j] << ' ';
out << '\n';
}
}