Pagini recente » Cod sursa (job #854760) | Cod sursa (job #733569) | Cod sursa (job #179005) | Cod sursa (job #1510433) | Cod sursa (job #1876549)
#include <bits/stdc++.h>
#define IT vector < int > :: iterator
#define NMAX 100005
using namespace std;
vector < int > gr[NMAX];
vector < int > gr2[NMAX];
vector < int > gr3[NMAX];
vector < int > postordine;
bool viz[NMAX];
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);
vector < int > :: reverse_iterator it5;
for (it5 = postordine.rbegin(); it5 != postordine.rend(); ++ it5)
if (viz[*it5]) {
++ 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;
}