Pagini recente » Cod sursa (job #3214878) | Cod sursa (job #1781365) | Cod sursa (job #2825942) | Cod sursa (job #1449771) | Cod sursa (job #928397)
Cod sursa(job #928397)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int N, M, cnt = -1;
vector <int> muchii[100011];
vector <int> transp[100011];
vector <int> noduri;
vector <int> Ans[100011];
void Citire ()
{
ifstream fin ("ctc.in");
fin >> N >> M;
for (int i = 0, a, b; i < M; i++)
{
fin >> a >> b;
muchii[a].push_back (b);
transp[b].push_back (a);
}
fin.close ();
}
int viz[100011];
void DFS1 (int nod)
{
viz[nod] = 1;
for (int i = 0; i < muchii[nod].size (); i++)
{
if (!viz[muchii[nod][i]])
DFS1 (muchii[nod][i]);
}
noduri.push_back (nod);
}
void Scriere ()
{
ofstream fout ("ctc.out");
fout << cnt + 1 << "\n";
for (int i = 0; i <= cnt; i++)
{
for (int j = 0; j < Ans[i].size (); j++)
fout << Ans[i][j] << " ";
fout << "\n";
}
fout.close ();
}
void DFS2 (int nod)
{
viz[nod] = 1;
Ans[cnt].push_back (nod);
for (int i = 0; i < transp[nod].size (); i++)
if (!viz[transp[nod][i]]) DFS2 (transp[nod][i]);
}
int main ()
{
Citire ();
for (int i = 1; i <= N; i++)
if (!viz[i]) DFS1 (i);
memset (viz, 0, sizeof (viz));
for (; !noduri.empty (); noduri.pop_back ())
if (!viz[noduri.back ()])
{
++cnt;
DFS2 (noduri.back ());
}
Scriere ();
return 0;
}