Pagini recente » Cod sursa (job #2179107) | Cod sursa (job #326241) | Cod sursa (job #2373655) | Cod sursa (job #2599491) | Cod sursa (job #2117762)
#include <fstream>
#include <vector>
#define NMAX 100005
#define MMAX 200005
using namespace std;
const char inname[] = "ctc.in";
const char outname[] = "ctc.out";
ifstream fin(inname);
ofstream fout(outname);
struct liste{
vector<int> vecini;
};
liste L[NMAX];
struct listetr{
vector<int> vecinitr;
};
struct elemente{
vector<int> elem;
};
elemente E[NMAX];
listetr LT[NMAX];
int viz[NMAX], viztr[NMAX], noduridfs[NMAX];
int i, j, n, lg, m, lgf;
void citire();
void dfs(unsigned int);
void dfsinvers(unsigned int);
int main(){
citire();
for(i=1; i<=n; i++)
if(viz[i] == 0)
dfs(i);
for(i=lg; i>=1; i--)
if(viztr[noduridfs[i]] == 0){
dfsinvers(noduridfs[i]);
lgf++;
}
fout << lgf << '\n';
for(i=0; i<lgf; i++){
for(j=0; j<E[i].elem.size(); j++)
fout << E[i].elem[j] << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}
void citire(){
int i, x, y;
fin >> n >> m;
for(i=1; i<=m; i++){
fin >> x >> y;
L[x].vecini.push_back(y);
LT[y].vecinitr.push_back(x);
}
}
void dfs(unsigned int x){
unsigned int i, aux;
viz[x] = 1;
for(i=0; i<L[x].vecini.size(); i++)
if(viz[L[x].vecini[i]] == 0){
aux = L[x].vecini[i];
dfs(aux);
}
lg++;
noduridfs[lg] = x;
}
void dfsinvers(unsigned int x){
unsigned int i, aux;
viztr[x] = 1;
E[lgf].elem.push_back(x);
for(i=0; i<LT[x].vecinitr.size(); i++)
if(viztr[LT[x].vecinitr[i]] == 0){
viztr[LT[x].vecinitr[i]] = 1;
aux = LT[x].vecinitr[i];
dfsinvers(aux);
}
}