Pagini recente » Cod sursa (job #519696) | Cod sursa (job #575193) | Cod sursa (job #164308) | Cod sursa (job #3180308) | Cod sursa (job #3002727)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> gr[200000] , gt[200000];
int top[200000] , in , n , m , x , y;
bool viz[200000];
vector <vector<int> >ctc;
vector <int> aux;
void dfs( int x ){
viz[x] = 1;
for(int i=0 ;i<gr[x].size();i ++){
int it=gr[x][i];
if(!viz[it]){
dfs(it);
}
}
top[in--] = x;
}
void dfst( int x ){
viz[x] = 0;
aux.push_back(x);
for(int i=0 ;i<gt[x].size();i++){
int it=gt[x][i];
if(viz[it]){
dfst(it);
}
}
}
int main(){
f >> n >> m;
in = n;
for(int j=1;j<=m;j++)
{
f>> x >> y;
gr[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1 ; i <= n ; i++){
if(!viz[i]) dfs(i);
}
for(int i = 1 ; i <= n ; i++){
if(viz[top[i]]){
aux.clear();
dfst(top[i]);
ctc.push_back(aux);
}
}
g<< ctc.size() << '\n';
for(int j=0;j<ctc.size();j++)
{for(int k=0;k<ctc[j].size();k++)
g<<ctc[j][k]<<" ";
g<<'\n';
}
return 0;
}