Pagini recente » Cod sursa (job #895240) | Cod sursa (job #1358508) | Cod sursa (job #2874509) | Cod sursa (job #2182013) | Cod sursa (job #1361862)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nrpost, nrsol;
int postordine[100005];
vector<int> V[100005], W[100005], sol[100005];
bool used[100005];
void DFS(int nod)
{
used[nod] = true;
for (vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
if (!used[*it])
DFS(*it);
postordine[++nrpost] = nod;
}
void DFSt(int nod)
{
used[nod] = false;
sol[nrsol].push_back(nod);
for (vector<int>::iterator it = W[nod].begin(); it != W[nod].end(); ++it)
if (used[*it])
DFSt(*it);
}
int main()
{
fin >> N >> M;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
W[nod2].push_back(nod1);
}
for (int i = 1; i <= N; ++i)
if (!used[i])
DFS(i);
for (int i = N; i >= 1; --i)
if (used[postordine[i]])
{
++nrsol;
DFSt(postordine[i]);
}
fout << nrsol << '\n';
for (int i = 1; i <= nrsol; ++i)
{
for (vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
fout << *it << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}