Pagini recente » Cod sursa (job #1144569) | Cod sursa (job #826497) | Cod sursa (job #2598237) | Cod sursa (job #1321077) | Cod sursa (job #2725179)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100001;
vector <int> a_s[N] , a_p[N] ;
vector <vector<int>> ctc ;
bitset <N> viz ;
int n , m , sol[N] , nrs , cc[N];
void dfs(int x)
{
viz[x] = 1;
for ( auto y: a_s[x] )
{
if ( !viz[y] )
{
dfs(y);
}
}
sol[++nrs] = x;
}
void dfs_p( int x )
{
viz[x] = 1;
cc[x] = ctc.size() - 1;
for ( auto y: a_p[x] )
{
if ( !viz[y] )
{
dfs_p(y);
}
}
}
int main()
{
in >> n >> m;
for ( int i = 0 ; i < m ; i++ )
{
int x, y;
in >> x >> y;
a_s[x].push_back(y);
a_p[y].push_back(x);
}
in.close();
for ( int i = 1 ; i <= n ; i++ )
{
if ( !viz[i] )
{
dfs(i);
}
}
viz.reset();
for ( int i = nrs ; i >= 1 ; i-- )
{
if ( !viz[sol[i]] )
{
vector <int> v;
ctc.push_back(v);
dfs_p(sol[i]);
}
}
out << ctc.size() << "\n";
for ( int i = 1 ; i <= n ; i++ )
{
ctc[cc[i]].push_back(i);
}
for ( auto comp: ctc )
{
for ( auto x: comp )
{
out << x << " ";
}
out << "\n" ;
}
out.close();
return 0;
}