Pagini recente » Cod sursa (job #2535856) | Cod sursa (job #208944) | Cod sursa (job #1736389) | Cod sursa (job #2083168) | Cod sursa (job #2928543)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
//Algoritmul lui Kosoraju
vector<vector<int>>lista;
vector<int>viz;
vector<vector<int>>transpusa;
stack<int>stiva;
vector<vector<int>>conexe;
int count;
void dfs(int nod){
viz[nod]=1;
for(auto & i:lista[nod]){
if(!viz[i]){
dfs(i);
}
}
stiva.push(nod);
}
void dfst(int nod){
viz[nod]=2;
conexe[count-1].push_back(nod);
for(auto & i:transpusa[nod]){
if(viz[i]!=2){
dfst(i);
}
}
}
int main() {
int n,m,x,y,nod;
f>>n>>m;
lista.resize(n+1);
viz.resize(n+1,0);
transpusa.resize(n+1);
conexe.resize(n+1);
//creez lista de adiacenta
while(f){
f>>x>>y;
lista[x].push_back(y);
}
//parcurg graf prin dfs
for(int i=1;i<=n;i++){
if(!viz[i]){
dfs(i);
}
}
//creez transpusa listei de adiacenta
for(int i=1;i<=n;i++){
for(auto & j:lista[i]){
transpusa[j].push_back(i);
}
}
//parcurg stiva si fac dfs pe transpusa listei de adiacenta
while(!stiva.empty()){
nod=stiva.top();
stiva.pop();
if(viz[nod]==1){
count++;
dfst(nod);
}
}
g<<count<<"\n";
for(int i=0;i<count;i++){
for(auto & z:conexe[i]){
g<<z<<" ";
}
g<<"\n";
}
return 0;
}