Pagini recente » Cod sursa (job #2467330) | Borderou de evaluare (job #365280) | Cod sursa (job #2890678) | Cod sursa (job #41490) | Cod sursa (job #1373371)
#include <fstream>
#include <vector>
#include <stack>
#define Max_Size 100009
using namespace std;
const char iname[] = "ctc.in";
const char oname[] = "ctc.out";
int N, M, ctc;
bool Viz[Max_Size];
vector < int > V[Max_Size], W[Max_Size], Sol[Max_Size];
stack < int > my_Stack;
void DF_Plus( int nod )
{
Viz[ nod ] = 1;
for(vector < int > :: iterator it = V[nod].begin(); it != V[nod].end(); ++it)
if(!Viz[ *it ]) DF_Plus( *it );
my_Stack.push( nod );
}
void DF_Minus( int nod )
{
Viz[nod] = 1;
Sol[ctc].push_back( nod );
for(vector < int > :: iterator it = W[nod].begin(); it != W[nod].end(); ++it)
if( !Viz[ *it ] ) DF_Minus( *it );
}
int main()
{
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);
}
for(int i = 1; i <= N; ++i)
if( !Viz[i]) DF_Plus(i);
for(int i = 1; i <= N; ++i) Viz[i] = 0;
while( !my_Stack.empty()) {
if( !Viz[ my_Stack.top() ]) {
++ctc;
DF_Minus( my_Stack.top() );
}
my_Stack.pop();
}
ofstream out( oname );
out << ctc << '\n';
for(int i = 1; i <= ctc; ++i) {
for(int j = 0; j < Sol[i].size(); ++j) out << Sol[i][j] << ' ';
out << '\n';
}
return 0;
}