Pagini recente » Cod sursa (job #1613606) | Cod sursa (job #707182) | Cod sursa (job #2930557) | Cod sursa (job #399132) | Cod sursa (job #2360822)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int N = 100001;
vector <int> s[N];
vector <int> p[N];
vector <int> ctc[N];
int n, m, nr = 0, st[N];
bool vizs[N], vizp[N];
ifstream in ("ctc.in");
ofstream out ("ctc.out");
void citire()
{
in >> n >> m;
int x, y;
for ( int i = 0; i < m; i++ )
{
in >> x >> y;
s[x].push_back(y);
p[y].push_back(x);
}
}
void dfss( int x )
{
vizs[x] = true;
for ( int i = 0; i < s[x].size(); i++ )
{
int y = s[x][i];
if ( !vizs[y] )
{
dfss(y);
}
}
st[++nr] = x;
}
void dfsp( int x, int nc )
{
ctc[nc].push_back(x);
vizp[x] = true;
for ( int i = 0; i < p[x].size(); i++ )
{
int y = p[x][i];
if ( !vizp[y] )
{
dfsp(y, nc);
}
}
}
int main()
{
citire();
for ( int i = 1; i <= n; i++ )
{
if ( !vizs[i] )
dfss(i);
}
int nc = 0;
for ( int i = n; i > 0; i-- )
{
if ( !vizp[st[i]] )
{
nc++;
dfsp(st[i], nc);
}
}
out << nc << "\n";
for( int i = 1; i <= nc; i++ )
{
for ( int j = 0; j < ctc[i].size(); j++ )
{
out << ctc[i][j] << " ";
}
out << "\n";
}
return 0;
}