Pagini recente » Cod sursa (job #1140134) | Cod sursa (job #2812146) | Cod sursa (job #1016493) | Cod sursa (job #947336) | Cod sursa (job #892542)
Cod sursa(job #892542)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
const int dim = 100004;
int N, M, NB, NR, low[dim], niv[dim];
vector <int> V[dim], R[dim];
stack <int> S;
void cit ()
{
fi >> N >> M;
for (int i = 1, x, y; i <= M; i++)
{
fi >> x >> y;
V[x].push_back (y);
//V[y].push_back (x);
}
}
void dfs (int n, int t)
{
low[n] = niv[n] = ++NR;
S.push (n);
for (int i = 0, f; i < V[n].size(); i++)
{
f = V[n][i];
if (niv[f] == 0)
{
dfs (f, n);
low[n] = min (low[n], low[f]);
}
else
{
low[n] = min (low[n], niv[f]);
}
}
if (niv[n] == low[n])
{
int f = n - 1;
NB++;
while (f != n)
{
f = S.top ();
S.pop ();
R[NB].push_back (f);
}
}
}
void afi ()
{
int i, j;
fo << NB << '\n';
for (i = 1; i <= NB; i++)
{
for (j = 0; j < R[i].size(); j++)
{
fo << R[i][j] << ' ';
}
fo << '\n';
}
}
int main ()
{
cit ();
for (int i = 1; i <= N; i++)
{
if (low[i] == 0)
{
dfs (i, 0);
}
}
afi ();
return 0;
}