Pagini recente » Cod sursa (job #1514736) | Cod sursa (job #40858) | Cod sursa (job #1669048) | Cod sursa (job #1044066) | Cod sursa (job #651336)
Cod sursa(job #651336)
#include <fstream>
#include <vector>
using namespace std;
ifstream fi ("ctc.in");
ofstream fo ("ctc.out");
const int dim = 200005;
vector <int> C[dim], V[dim];
int N, M, NC, S[dim], niv[dim], low[dim], viz[dim];
void cit ()
{
fi >> N >> M;
for (int i = 1, x, y; i <= M; i++)
{
fi >> x >> y;
V[x].push_back (y);
}
}
void dfs (int n, int t)
{
niv[n] = low[n] = niv[t] + 1;
viz[n] = 1;
S[++S[0]] = 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[f], low[n]);
}
else if (viz[f] == 1)
{
low[n] = min (low[f], low[n]);
}
}
if (niv[n] == low[n])
{
NC++;
while (S[S[0] + 1] != n)
{
viz[S[S[0]]] = 0;
C[NC].push_back (S[S[0]]);
S[0]--;
}
}
}
void afi ()
{
fo << NC << '\n';
for (int i = 1; i <= NC; i++)
{
for (int j = 0; j < C[i].size(); j++)
fo << C[i][j] << ' ';
fo << '\n';
}
}
int main ()
{
cit ();
for (int i = 1; i <= N; i++)
if (niv[i] == 0)
dfs (i, 0);
afi ();
return 0;
}