Pagini recente » Cod sursa (job #3152481) | Cod sursa (job #2708719) | Cod sursa (job #2708670) | Cod sursa (job #3141682) | Cod sursa (job #1876526)
#include <bits/stdc++.h>
#define IT vector < int > :: iterator
#define NMAX 50002
using namespace std;
vector < int > gr[NMAX];
vector < int > gr2[NMAX];
vector < int > gr3[NMAX];
vector < int > postordine;
bool viz[50001];
void DFS(int x)
{
viz[x] = 1;
for (IT it = gr[x].begin(); it != gr[x].end(); ++ it)
if (!viz[*it])
DFS(*it);
postordine.push_back(x);
}
void DFST(int x, int y)
{
viz[x] = 0;
gr3[y].push_back(x);
for (IT it = gr2[x].begin(); it != gr2[x].end(); ++ it)
if (viz[*it])
DFST(*it, y);
}
int main()
{
int n, a, b, m;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> n >> m;
int nr = 0;
for (int i = 1 ; i <= m; ++ i) {
fin >> a >> b;
gr[a].push_back(b);
gr2[b].push_back(a);
}
for (int i = 1; i <= n; ++ i)
if (!viz[i])
DFS(i);
for (IT it = postordine.end() - 1; it >= postordine.begin(); -- it)
if (viz[*it]) {
++ nr;
DFST(*it5, nr);
}
fout << nr << "\n";
for (int i = 1; i <= nr; ++ i) {
for (IT it = gr3[i].begin(); it != gr3[i].end(); ++ it)
fout << *it << " ";
fout << "\n";
}
return 0;
}