Pagini recente » Cod sursa (job #798451) | Cod sursa (job #647370) | Cod sursa (job #387928) | Cod sursa (job #2716281) | Cod sursa (job #2175709)
#include <bits/stdc++.h>
using namespace std;
int n, a, b, m, ctc;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector < int > G[100005], GT[100005], rsp[100005];
bitset <100005> fv;
stack < int > st;
void dfs_1( int nod )
{
fv[nod] = true;
for ( auto i : G[nod] )
{
if ( fv[i] == false )
{
dfs_1( i );
}
}
st.push(nod);
}
void dfs_2( int nod )
{
fv[nod] = true;
for ( auto i : GT[nod] )
{
if ( fv[i] == false )
{
dfs_2( i );
}
}
rsp[ctc].push_back( nod );
}
int main ()
{
f>>n>>m;
for ( int i = 1; i <= m ; i++ )
{
f>>a>>b;
G[a].push_back(b);
GT[b].push_back(a);
}
for ( int i = 1 ; i <= n ; i++ )
{
if ( fv[i] == false )
{
dfs_1( i );
}
}
fv.reset();
while ( !st.empty() )
{
if ( fv[st.top()] == false )
{
ctc++;
dfs_2( st.top() );
}
st.pop();
}
g<<ctc<<'\n';
for ( int i = 1; i <= ctc ; i++ )
{
for ( auto it : rsp[i] )
{
g<<it<<" ";
}
g<<'\n';
}
}