Pagini recente » Cod sursa (job #1696344) | Cod sursa (job #726848) | Cod sursa (job #2257461) | Cod sursa (job #1191) | Cod sursa (job #2816089)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
class Graf {
int nr_noduri, nr_muchii;
vector<int> muchii[200005];
vector<int> muchii_graf_transpus[200005];
vector<int> CTC[100005];
queue<int> coada;
int vizitat[100005] = {};
int vizitat_graf_transpus[100005] = {};
int timp = 0;
int nr_ctc = 0;
stack<int> s;
public:
//citirea din fisier a muchiilor
void citire() {
int x, y;
in >> nr_noduri;
in >> nr_muchii;
for (int i = 1; i <= nr_muchii; ++i) {
in >> x >> y;
muchii[x].push_back(y);
//muchii[y].push_back(x);
//adaugare pentru construirea grafului transpus
muchii_graf_transpus[y].push_back(x);
}
}
//parcurgere in adancime
void dfs(int x){
vizitat[x] = 1;
for(auto val : muchii[x])
if(!vizitat[val])
dfs(val);
//adaugare varfuri in stiva dupa momentul terminarii vizitarii acestora
s.push(x);
}
//parcurgere in adancime graf transpus
//fara paramentru deoarece adaugam noduri din stiva
void dfs_graf_transpus(int x){
vizitat_graf_transpus[x] = 1;
CTC[nr_ctc].push_back(x);
for(auto val : muchii_graf_transpus[x])
if(!vizitat_graf_transpus[val])
dfs_graf_transpus(val);
}
void kosaraju(){
Graf::citire();
Graf::dfs(1);
while(s.size()) {
int x = s.top();
if(!vizitat_graf_transpus[x])
++nr_ctc,dfs_graf_transpus(x);
s.pop();
}
out << nr_ctc << endl;
for(int i = 1; i <= nr_ctc; ++i){
for(auto val : CTC[i])
out << val << " ";
out << endl;
}
}
};
int main() {
Graf G;
G.kosaraju();
return 0;
}