Pagini recente » Cod sursa (job #2729533) | Cod sursa (job #2948971) | Cod sursa (job #1236098) | Cod sursa (job #2436642) | Cod sursa (job #1250755)
#include <fstream>
#include <vector>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, vfi;
vector<int> A[NMAX], At[NMAX], Rez[NMAX];
bool uz[NMAX], uz2[NMAX];
int postordine[NMAX], nr, lgrez = 1, lg2;
void init();
void DFS1(int);
void DFST(int);
int main(){
init();
int i;
for(i = 1; i<=n; ++i){
if(!uz[i]) DFS1(i);
}
for(i = nr; i>=1; --i){
if(!uz2[postordine[i]]){
lg2= 0;
DFST(postordine[i]);
lgrez++;
}
}
lgrez--; int j;
fout<<lgrez<<'\n';
for(i = 1; i <= lgrez; ++i){
for(j = 0; j< Rez[i].size(); ++j)
fout<<Rez[i][j]<<" ";
fout<<'\n';
}
return 0;
}
void init(){
int x, y, i;
fin>>n>>m;
for(i = 0;i < m;i++){
fin>>x>>y;
A[x].push_back(y);
At[y].push_back(x);
}
}
void DFS1(int k){
int i;
uz[k] = 1;
for(i = 0; i< A[k].size(); ++i)
if(!uz[A[k][i]])
DFS1(A[k][i]);
postordine[++nr] = k;
}
void DFST(int k){
int i;
uz2[k] = 1;
Rez[lgrez].push_back(k);
for(i = 0; i< At[k].size(); ++i){
if(!uz2[At[k][i]]){
DFST( At[k][i] );
}
}
}