Pagini recente » Cod sursa (job #27161) | Cod sursa (job #754615) | Cod sursa (job #1480579) | Cod sursa (job #775967) | Cod sursa (job #2925289)
#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(100001);
vector<vector<int>> ctc;
vector <int> v, index(1000), pozmin(1000), viz(1000);
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;
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;
}