Pagini recente » Cod sursa (job #1524889) | Cod sursa (job #3182644) | Cod sursa (job #236747) | Cod sursa (job #3194783) | Cod sursa (job #1234652)
#include <fstream>
#include <vector>
#include <queue>
const int NMAX = 100005;
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,componenta[NMAX],numar_elemente,stiva[NMAX],elemente_stiva,nr;
vector <int> v[NMAX],vt[NMAX],componente[NMAX];
bool removed[NMAX],used[NMAX],used_aux[NMAX];
void DFS(int nod)
{
used[nod] = true;
elemente_stiva++;
stiva[elemente_stiva] = nod;
for (int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if (!used[vecin])
DFS(vecin);
}
}
void DFST(int nod)
{
used_aux[nod] = true;
elemente_stiva++;
stiva[elemente_stiva]++;
if (used[nod])
{
componente[nr].push_back(nod);
}
for (int i = 0; i < vt[nod].size(); ++i)
{
int vecin = vt[nod][i];
if (!used_aux[vecin])
DFST(vecin);
}
}
void search(int nod)
{
nr++;
for (int i = 1; i <= elemente_stiva; ++i)
used[stiva[i]] = false;
elemente_stiva = 0;
DFS(nod);
DFST(nod);
numar_elemente = componente[nr].size();
for (int i = 0; i < numar_elemente; ++i)
{
removed[componente[nr][i]] = true;
}
}
void afisare()
{
g << nr << '\n';
for (int i = 1; i <= nr; ++i)
{
for (int j = 0; j < componente[i].size(); ++j)
g << componente[i][j] << " ";
g << '\n';
}
}
int main()
{
f >> N >> M;
for (int i = 1; i <= M; ++i)
{
int x, y;
f >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
{
if(!removed[i])
{
search(i);
}
}
afisare();
f.close();
g.close();
return 0;
}