Pagini recente » Cod sursa (job #2146506) | Cod sursa (job #1460046) | Cod sursa (job #1628084) | Cod sursa (job #824129) | Cod sursa (job #2103733)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <algorithm>
#define mx 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int nrcomponente;
int val[mx],i,x,y,n,m;
list < int > v[mx],componente[mx];
int Tata=1;
stack < int > st;
bool stiva[mx];
int low[mx];
void dfs(int from){
int nod;
val[from]=Tata;
low[from]=Tata;
st.push(from);
stiva[from]=true;
Tata++;
list < int > ::iterator it;
for( it=v[from].begin() ; it!=v[from].end() ; it++){
nod=*it;
if(val[nod]==0) {
dfs(nod);
low[from]=min(low[from],low[nod]);
}
else if(stiva[nod]==1){
low[from]=min(low[from],val[nod]);
}}
if(low[from]==val[from]){
nrcomponente++;
nod=st.top();
do{
nod=st.top();
componente[nrcomponente].push_back(nod);
st.pop();
stiva[nod]=false;
}while(nod!=from);
}
}
int main(){
in>>n>>m;
for(i=1;i<=m;++i){
in>>x>>y;
v[x].push_back(y);
}
for(i=1;i<=n;++i){
if(val[i]==0) dfs(i);
}
out<<nrcomponente<<'\n';
list <int> ::iterator itt;
for(i=nrcomponente;i>=1;i--){
for(itt=componente[i].begin() ; itt!=componente[i].end() ; itt++){
out<<*itt<<' ';
}out<<'\n';
}
return 0;
}