Pagini recente » Cod sursa (job #930596) | Cod sursa (job #880487) | Cod sursa (job #2471958) | Cod sursa (job #499232) | Cod sursa (job #3164744)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax = 100003;
int n, m, index;
bool vizTop[nmax];
bool vizCTC[nmax];
vector <int> g[nmax];
vector <int> gTranspus[nmax];
vector <int> ctc[nmax];
stack <int> elementeTopSortate;
void dfs(int nod);
void dfsTranspus(int nod);
void read(void);
int main(){
int i, j;
read();
for(i = 1; i <= n; i++)
if(!vizTop[i])
dfs(i);
while(!elementeTopSortate.empty()){
i = elementeTopSortate.top();
elementeTopSortate.pop();
if(!vizCTC[i]){
dfsTranspus(i);
index++;
}
}
fout<<index<<"\n";
for(i = 0; i < index; i++){
for(j = 0; j < ctc[i].size(); j++)
fout<<ctc[i][j]<<" ";
fout<<"\n";
}
}
void read(void){
int i, j;
fin>>n>>m;
while(m--){
fin>>i>>j;
g[i].push_back(j);
gTranspus[j].push_back(i);
}
}
void dfs(int nod){
int i, vecin;
vizTop[nod]++;
for(i = 0; i < g[nod].size(); i++){
vecin = g[nod][i];
if(!vizTop[vecin])
dfs(vecin);
}
elementeTopSortate.push(nod);
}
void dfsTranspus(int nod){
int i, vecin;
vizCTC[nod] = true;
ctc[index].push_back(nod);
for(i = 0; i < gTranspus[nod].size(); i++){
vecin = gTranspus[nod][i];
if(!vizCTC[vecin])
dfsTranspus(vecin);
}
}