Pagini recente » Cod sursa (job #1892539) | Cod sursa (job #1969733) | Istoria paginii utilizator/buicescu-bungiu-postavaru | Cod sursa (job #1697061) | Cod sursa (job #535689)
Cod sursa(job #535689)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, nrc, c; // nrc = nr de componente conexe, c = contor in stiva
vector<vector<int> > G;
vector<vector<int> > T;
vector<vector<int> > sol;
int a[100001]; //stiva
bool s[100001]; // sirul de selectati in graful normal;
bool s1[100001]; //sirul de selectati in graful transpus;
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);
sol.resize(n+1);
int x, y;
while( fin >> x >> y )
{
G[x].push_back(y);
T[y].push_back(x);
}
}
void Solve()
{
c = 0;
for( int i = 1; i <= n; ++i )
if( !s[i] )
{
DF(i);
c++;
a[c] = i;
}
/*
for( int i = 1; i <= n; ++i )
fout << a[i] << ' ';
fout << '\n';
*/
for( int i = n; i >= 1; --i )
if( !s1[ a[i] ] )
{
nrc++;
DFT( a[i] );
}
fout << nrc << '\n';
for( int i = 1; i <= nrc; ++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] );
c++;
a[c] = G[x][i];
}
}
void DFT( int x )
{
s1[x] = true;
sol[nrc].push_back( x );
for( int i = 0; i < T[x].size(); ++i )
if( !s1[ T[x][i] ] )
DFT( T[x][i] );
}