Pagini recente » Cod sursa (job #33489) | Cod sursa (job #719621) | Cod sursa (job #3212138) | Cod sursa (job #550128) | Cod sursa (job #3271789)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Nmax = 100005;
struct nod{
bool vizitat;
vector<int> vecini;
vector<int> vecini_transpus;
};
int timp, indice_componenta;
int nr_noduri, nr_muchii, ordine_vizitat[Nmax];
nod graf[Nmax];
vector<int> componente[Nmax];
void citire(){
int nod1, nod2;
fin >> nr_noduri >> nr_muchii;
for(int i = 1; i <= nr_muchii; i++){
fin >> nod1 >> nod2;
graf[nod1].vecini.push_back(nod2);
graf[nod2].vecini_transpus.push_back(nod1);
}
}
void dfs_marcare_timpi(int nod){
graf[nod].vizitat = 1;
for(int vecin : graf[nod].vecini){
if(!graf[vecin].vizitat){
dfs_marcare_timpi(vecin);
}
}
ordine_vizitat[++timp] = nod;
}
void resetare_vizitare(){
for(int i = 1; i <= nr_noduri; i++){
graf[i].vizitat = 0;
}
}
void dfs_transpus(int nod){
graf[nod].vizitat = 1;
for(int vecin : graf[nod].vecini_transpus){
if(!graf[vecin].vizitat){
dfs_transpus(vecin);
}
}
componente[indice_componenta].push_back(nod);
}
void kosaraju(){
int nod;
timp = 0;
for(int i = 1; i <= nr_noduri; i++){
if(!graf[i].vizitat){
dfs_marcare_timpi(i);
}
}
resetare_vizitare();
indice_componenta = 0;
for(int i = nr_noduri; i >= 1; i--){
nod = ordine_vizitat[i];
if(!graf[nod].vizitat){
indice_componenta++;
dfs_transpus(nod);
}
}
}
void afisare(){
fout << indice_componenta << '\n';
for(int i = 1; i <= indice_componenta; i++){
for(int nod : componente[i]){
fout << nod << ' ';
}
fout << '\n';
}
}
int main(){
citire();
kosaraju();
afisare();
return 0;
}