Pagini recente » Cod sursa (job #1216451) | Cod sursa (job #2731787) | Cod sursa (job #2138613) | Cod sursa (job #72972) | Cod sursa (job #1107096)
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
int N,M,index[100100],viz[100100],link[100100],sol[100100],nr,pozsol=1,nrsolutii;
vector <int> v[100100],Stack;
void citire() {
ifstream in("ctc.in");
int i,x,y;
in>>N>>M;
for(i=1;i<=M;i++) {
in>>x>>y;
v[x].push_back(y);
}
in.close();
}
void dfs(int nod) {
int vecin,i;
viz[nod]=1;
index[nod]=nr;
link[nod]=nr;
nr++;
Stack.push_back(nod);
for(i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if(!index[vecin]){
dfs(vecin);
if(link[nod]>link[vecin])
link[nod]=link[vecin];
}
else
if(viz[vecin])
if(link[nod]>link[vecin])
link[nod]=link[vecin];
}
if(link[nod]==index[nod]) {
sol[pozsol]=Stack.back();
viz[sol[pozsol]]=0;
pozsol++;
while(Stack.back()!=nod){
Stack.pop_back();
sol[pozsol]=Stack.back();
viz[sol[pozsol]]=0;
pozsol++;
}
Stack.pop_back();
pozsol++;
nrsolutii++;
}
}
void solve() {
int i;
nr=1;
for(i=1;i<=N;i++)
if(!index[i])
dfs(i);
}
void afisare() {
ofstream out("ctc.out");
int i;
out<<nrsolutii<<'\n';
for(i=1;i<=pozsol-1;i++)
if(sol[i]==0)
out<<'\n';
else
out<<sol[i]<<' ';
out.close();
}
int main () {
citire();
solve();
afisare();
return 0;
}