Pagini recente » Cod sursa (job #1617052) | Cod sursa (job #1004749) | Cod sursa (job #2754573) | Cod sursa (job #847735) | Cod sursa (job #535539)
Cod sursa(job #535539)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> st;
bool s[100001];
bool s1[100001];
int n, m, nr, p;
vector<vector<int> > G;
vector<vector<int> > T;
vector<vector<int> > sol;
void Read();
void Solve();
void DF( int x );
void DFT( int x );
int main()
{
Read();
Solve();
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
G.resize(n+1);
T.resize(n+1);
st.resize(n+1);
sol.resize(n+1);
int x, y;
while( fin >> x >> y )
{
G[x].push_back(y);
T[y].push_back(x);
}
/*
for( int i = 1; i <= n; ++i )
{
fout << i <<": ";
for( int j = 0; j < G[i].size(); ++j )
fout << G[i][j] << ' ';
fout << '\n';
}
*/
}
void Solve()
{
nr = 0;
p = 0;
for( int i = 1; i <= n; ++i )
if( !s[i] )
{
DF(i);
st[++p] = i;
}
for( int i = n; i > 0; --i )
if( !s1[ st[i] ] )
{
nr++;
DFT( st[i] );
}
/*
for( int i = n; i > 0; --i )
fout << st[i] << ' ';
*/
fout << nr << '\n';
for( int i = 1; i <= nr; ++i )
{
for( int j = 0; j < sol[i].size(); ++j )
fout << sol[i][j] << ' ';
fout << '\n';
}
}
void DF( int x )
{
s[x] = true;
for( int i = 0; i < G[x].size(); ++i )
if( !s[ G[x][i] ] )
{
DF( G[x][i] );
st[++p] = G[x][i];
}
}
void DFT( int x )
{
s1[x] = true;
sol[nr].push_back( x );
for( int i = 0; i < T[x].size(); ++i )
if( !s1[ T[x][i] ] )
{
//sol[nr].push_back( T[x][i] );
DFT( T[x][i] );
}
}