Pagini recente » Cod sursa (job #1364090) | Cod sursa (job #1180151) | Cod sursa (job #1229789) | Cod sursa (job #1206632) | Cod sursa (job #2928880)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n,m,compConexe,ind;
vector<vector<int>> adiacenta,componente;
stack<int> noduri;
vector<bool> stiva;
vector<int> index,lowlink;
ifstream f("ctc.in");
ofstream g("ctc.out");
void strongconnect(int nod){
lowlink[nod]=index[nod]=ind;
ind++;
noduri.push(nod);
stiva[nod]=true;
for(int i = 0; i<adiacenta[nod].size();++i){
if(index[adiacenta[nod][i]]==-1){
strongconnect(adiacenta[nod][i]);
lowlink[nod]=min(lowlink[nod],lowlink[adiacenta[nod][i]]);
}
else
if(stiva[adiacenta[nod][i]]){
lowlink[nod]=min(lowlink[nod],index[adiacenta[nod][i]]);
}
}
if(lowlink[nod]==index[nod]){
compConexe++;
int aux;
do{
aux=noduri.top();
componente[compConexe].push_back(aux);
stiva[aux]=false;
noduri.pop();
}while(aux!=nod);
}
}
int main(){
f>>n>>m;
int a,b;
adiacenta.resize(n+1);
componente.resize(n+1);
lowlink.resize(n+1);
stiva.resize(n+1,false);
index.resize(n+1,-1);
for (int i = 0; i < m; ++i) {
f>>a>>b;
adiacenta[a].push_back(b);
}
for(int i=1;i<=n;++i){
if(index[i]==-1)
strongconnect(i);
}
g<<compConexe<<'\n';
for(int i=1;i<=compConexe;++i){
for (int j = 0; j < componente[i].size(); ++j) {
g<< componente[i][j]<<' ';
}
g<<'\n';
}
return 0;
}