Pagini recente » Cod sursa (job #2252061) | Cod sursa (job #800450) | Cod sursa (job #2111338) | Cod sursa (job #1249492) | Cod sursa (job #300174)
Cod sursa(job #300174)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define INPUT "ctc.in"
#define OUTPUT "ctc.out"
const long NMAX = 100001;
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
long N, M, cont, final;
long mindf[ NMAX ], nrdf[ NMAX ];
vector<long> List[ NMAX ], Final[ NMAX ];
stack<long> stk;
bool viz[ NMAX ], added[ NMAX ];
void readData()
{
long Node1, Node2;
fscanf(fin, "%ld %ld", &N, &M);
for(long i = 1; i <= M; ++i)
{
fscanf(fin, "%ld %ld", &Node1, &Node2);
List[ Node1 ].push_back(Node2);
}
}
void tarjan(long Node)
{
nrdf[ Node ] = cont;
mindf[ Node ] = cont;
++cont;
stk.push(Node);
added[ Node ] = 1;
vector<long>::iterator it;
for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
{
if(nrdf[ *it ] == -1 || added[ *it ])
if(nrdf[ *it ] == -1) tarjan(*it);
mindf[ Node ] = min( mindf[ Node ], mindf[ *it ]);
}
long nnod;
if(mindf[ Node ] == nrdf[ Node ])
{
++final;
do{
nnod = stk.top();
stk.pop();
Final[ final ].push_back(nnod);
}while(nnod != Node);
}
}
int main()
{
readData();
cont = 0;
final = 0;
vector<long>::iterator it;
for(long i = 1; i <= N; ++i)
nrdf[ i ] = -1, mindf[ i ] = -1;
for(long i = 1; i <= N; ++i)
if(!viz[ i ])
tarjan(i);
fprintf(fout, "%ld\n", final);
for(long i = 1; i <= final; ++i)
{
for(it = Final[ i ].begin(); it != Final[ i ].end(); ++it)
fprintf(fout, "%ld ", *it);
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}