Pagini recente » Cod sursa (job #2076829) | Cod sursa (job #97027) | Clasament preONI 2007, Runda 2, Clasele 11-12 | Cod sursa (job #3152107) | Cod sursa (job #819694)
Cod sursa(job #819694)
#include <fstream>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
const int dim = 100005;
int N, niv[dim], low[dim];
vector <int> V[dim], r;
stack <int> S;
vector <vector <int> > R;
void cit ()
{
int x, y, m;
fi >> N >> m;
while ( m -- )
{
fi >> x >> y;
V[x].push_back (y);
}
}
void dfs (int n)
{
int f;
low[n] = niv[n] = ++niv[0];
S.push (n);
for (int i = 0; i < V[n].size(); i++)
{
f = V[n][i];
if (niv[f] == 0)
{
dfs (f);
low[n] = min (low[n], low[f]);
}
else if (niv[f] != -1)
{
low[n] = min (low[n], niv[f]);
}
}
if (niv[n] == low[n])
{
while (!r.empty())
r.pop_back ();
do {
f = S.top ();
S.pop ();
r.push_back (f);
niv[f] = -1;
} while (f != n);
R.push_back (r);
}
}
void rez ()
{
int i, j;
for (i = 1; i <= N; i++)
if (niv[i] == 0)
dfs (i);
fo << R.size () << '\n';
for (i = 0; i < R.size(); i++)
{
for (j = 0; j < R[i].size (); j++)
fo << R[i][j] << ' ';
fo << '\n';
}
}
int main ()
{
cit ();
rez ();
return 0;
}