Pagini recente » Cod sursa (job #1127085) | Cod sursa (job #127781) | Cod sursa (job #1737676) | Cod sursa (job #1007755) | Cod sursa (job #611636)
Cod sursa(job #611636)
#include<fstream>
#include<iostream>
#include<vector>
#define mx 200200
using namespace std;
vector<int> v[mx],stiva,solutie,stop;
int lnk[mx],vizitat[mx],indice[mx],n,nr=1;
long long clo=clock();
void afis() {
int i,j=0,m=solutie.size();
ofstream out("ctc.out");
out<<stop.size()<<'\n';
for(i=0;i<m;i++)
{out<<solutie[i]<<" ";
if(stop[j]==i)
out<<'\n',j++;
}
out.close();
}
void DFS(int nod) {
int vecin,i,m=v[nod].size();
vizitat[nod]=1;
indice[nod]=nr;
lnk[nod]=nr++;
stiva.push_back(nod);
for(i=0;i<m;i++)
{vecin=v[nod][i];
if(!vizitat[vecin])
DFS(vecin);
lnk[nod]=min(lnk[nod],lnk[vecin]);
}
if(lnk[nod]==indice[nod])
{solutie.push_back(stiva.back());
while(stiva.back()!=nod)
{stiva.pop_back();
solutie.push_back(stiva.back());
}
stiva.pop_back();
stop.push_back(solutie.size()-1);
}
}
void citire() {
int i,m,x,y;
ifstream in("ctc.in");
in>>n>>m;
for(i=0;i<m;i++)
{in>>x>>y;
v[x].push_back(y);
}
in.close();
}
int main() {
int i;
citire();
for(i=1;i<=n;i++)
if(!vizitat[i])
DFS(i);
afis();
cout<<clock()-clo<<'\n';
return 0;
}