Pagini recente » Cod sursa (job #924518) | Cod sursa (job #2292583) | Cod sursa (job #1678419) | Cod sursa (job #2578869) | Cod sursa (job #1791671)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("ctc.in");
ofstream t ("ctc.out");
struct nod{
int index,lowlink;
bool available=true,stacked=false;
vector <int> vecini;};
int n,m,indexare=0;
vector <int> stack;
vector < vector<int> > solutie;
vector <nod> v(100010);
void citire(){
int x,y;
f>>n>>m;
for (int i=0;i<m;++i)
f>>x>>y,v[x-1].vecini.push_back(y-1);
}
void unload(int nod){
int a;
vector <int> aux;
do{
a=stack.back();
stack.pop_back();
aux.push_back(a);
v[a].stacked=false;
}while (a!=nod);
solutie.push_back(aux);
}
void dfs(int x){
v[x].available=false;
v[x].index=v[x].lowlink=indexare++;
stack.push_back(x);
v[x].stacked=true;
for (unsigned i=0;i<v[x].vecini.size();++i)
if (v[v[x].vecini[i]].available)
dfs(v[x].vecini[i]),v[x].lowlink=min(v[x].lowlink,v[v[x].vecini[i]].lowlink);
else if (v[v[x].vecini[i]].stacked)
v[x].lowlink=min(v[x].lowlink,v[v[x].vecini[i]].lowlink);
if (v[x].lowlink==v[x].index)
unload(x);
}
int main()
{
citire();
for (int i=0;i<n;++i)
if (v[i].available)
dfs(i);
t<<solutie.size()<<'\n';
for(unsigned i=0;i<solutie.size();++i){
for (unsigned j=0;j<solutie[i].size();++j)
t<<1+solutie[i][j]<<" ";
t<<'\n';
}
return 0;
}