Pagini recente » Cod sursa (job #2767429) | Cod sursa (job #1864887) | Cod sursa (job #749134) | Cod sursa (job #1889399) | Cod sursa (job #2926485)
//complexitate: O(n+m)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, poz=0;
vector<vector<int>> lista_adiacenta;
vector<vector<int>> ctc;
vector <int> v, index, pozmin, viz;
stack <int> stiva;
void tarjan(int x){
stiva.push(x);
index[x]=poz;
pozmin[x]=poz;
poz++;
viz[x]=1;
for(auto i: lista_adiacenta[x]){
if(index[i]==-1){
tarjan(i);
pozmin[x]=min(pozmin[i], pozmin[x]);
}
else if(viz[i]==1){
pozmin[x]=min(pozmin[i], pozmin[x]);
}
}
if(index[x]==pozmin[x]){
int p;
do{
p=stiva.top();
stiva.pop();
viz[p]=0;
v.push_back(p);
}while(p!=x);
ctc.push_back(v);
v.clear();
}
}
int main()
{
int x,y;
fin>>n>>m;
lista_adiacenta.resize(n+1);
index.resize(n+1,-1);
pozmin.resize(n+1,0);
viz.resize(n+1,0);
// for(int i = 1; i <= n; i++)
// index[i] = -1;
// index.assign(n, -1);
for(int i=1; i<=m; i++){
fin>>x>>y;
lista_adiacenta[x].push_back(y);
}
for(int i=1; i<=n; i++){
if(index[i]==-1)
tarjan(i);
}
fout<<ctc.size()<<'\n';
for(auto i1=0; i1<ctc.size(); i1++){
for(auto i2: ctc[i1])
fout<<i2<<" ";
fout<<'\n';
}
return 0;
}