Pagini recente » Autentificare | Cod sursa (job #1288591) | Cod sursa (job #1067645) | Cod sursa (job #2201151) | Cod sursa (job #2853491)
#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MOD 1000000007
using namespace std ;
ifstream cin ("ctc.in") ;
ofstream cout ("ctc.out") ;
vector<int> v[100009], invers[100009] ;
int n, frecv[100009] ;
deque<int> dq ;
void fil(int nod)
{
if(frecv[nod])return ;
frecv[nod] = 1 ;
for(int f = 0 ; f < v[nod].size() ; f ++)
fil(v[nod][f]) ;
dq.push_back(nod) ;
}
vector<vector<int> > rez ;
vector<int> aux ;
void fil2(int nod)
{
if(frecv[nod])return ;
frecv[nod] = 1 ;
for(int f = 0 ; f < invers[nod].size() ; f ++)
fil2(invers[nod][f]) ;
aux.push_back(nod) ;
}
int main()
{
int q ;
cin >> n >> q ;
while(q --)
{
int a, b ;
cin >> a >> b ;
v[a].push_back(b) ;
invers[b].push_back(a) ;
}
for(int f = 1 ; f <= n ; f ++)
if(!frecv[f])fil(f) ;
/// inversam graful
for(int f = 1 ; f <= n ; f ++)
frecv[f] = 0 ;
while(dq.size())
{
int nod = dq.back() ;
if(frecv[nod])dq.pop_back() ;
else
{
fil2(nod) ;
rez.push_back(aux) ;
aux.clear() ;
}
}
cout << rez.size() << endl ;
for(int f = 0 ; f < rez.size() ; f ++)
{
for(int e = 0 ; e < rez[f].size() ; e ++)
cout << rez[f][e] << " " ;
cout << '\n' ;
}
return 0 ;
}