Pagini recente » Cod sursa (job #2023686) | Istoria paginii runda/hertzalaiiii/clasament | Cod sursa (job #2947089) | Atasamentele paginii Clasament hlo_10_vacanta | Cod sursa (job #1650840)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;
int n, m, numComp;
int i, j, x, y;
bool vizG[nmax], vizGT[nmax];
vector <int> G[nmax], GT[nmax];
vector <int> sol[nmax];
int postordine[nmax];
void dfsG(int nod)
{
vizG[nod] = true;
for (int i = 0; i < G[nod].size(); i++)
if (!vizG[G[nod][i]])
dfsG(G[nod][i]);
postordine[ ++postordine[0] ] = nod;
}
void dfsGT(int nod)
{
vizGT[nod] = true;
sol[numComp].push_back(nod);
for (int i = 0; i < GT[nod].size(); i++)
if (!vizGT[GT[nod][i]])
dfsGT(GT[nod][i]);
}
int main()
{
ifstream fi("ctc.in");
ofstream fo("ctc.out");
fi >> n >> m;
for (i = 1; i <= m; i++)
{
fi >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for (i = 1; i <= n; i++)
if (!vizG[i])
dfsG(i);
for (i = postordine[0]; i > 0; i--)
{
int currNode = postordine[i];
if (!vizGT[currNode])
{
numComp++;
dfsGT(currNode);
}
}
fo << numComp << "\n";
for (i = 1; i <= numComp; i++)
{
for (j = 0; j < sol[i].size(); j++)
fo << sol[i][j] << " ";
fo << "\n";
}
fi.close();
fo.close();
return 0;
}