Pagini recente » Cod sursa (job #2094440) | Cod sursa (job #285038) | Cod sursa (job #1529629) | Cod sursa (job #2151138) | Cod sursa (job #1921010)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100010
using namespace std;
int n, m;
vector <int> G[nmax];
vector <int> GT[nmax];
vector <int> tc[nmax];
vector <bool> viz(nmax);
vector <int> postord(nmax);
void read()
{
ifstream f("ctc.in");
f >> n >> m;
for(int i=0, x, y; i<m; ++i)
{
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
f.close();
}
int x, nrctc;
void dfs(int nod)
{
viz[nod] = true;
for(int i=0; i<G[nod].size(); ++i)
{
if(!viz[G[nod][i]])
dfs(G[nod][i]);
}
postord[++x] = nod;
}
void dfst(int nod)
{
viz[nod] = false;
tc[nrctc].push_back(nod);
for(int i=0; i<GT[nod].size(); ++i)
{
if(viz[GT[nod][i]])
dfst(GT[nod][i]);
}
}
void solve()
{
for(int i=1; i<=n; ++i)
{
if(!viz[i])
dfs(i);
}
for(int i=n; i; --i)
{
if(viz[postord[i]])
{
++nrctc;
dfst(postord[i]);
}
}
}
void out()
{
ofstream g("ctc.out");
g << nrctc << '\n';
for(int i=1; i<=nrctc; ++i)
{
for(int j=0; j<tc[i].size(); ++j)
g << tc[i][j] << ' ';
g << '\n';
}
g.close();
}
int main()
{
read();
solve();
out();
return 0;
}