Pagini recente » Atasamentele paginii vacanta_10_3 | Cod sursa (job #819994) | Cod sursa (job #2323392) | Cod sursa (job #2263700) | Cod sursa (job #1968028)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,index=1,ind[100001],ll[100001];
vector<int>con,a[100001];
stack<int>s;
vector<vector<int>>C;
bool st[100001];
void scn(int k){
ind[k]=index;
ll[k]=index;
index++;
s.push(k);
st[k]=true;
vector <int>::iterator it;
for(it=a[k].begin();it!=a[k].end();it++){
if(ind[*it]==0){
scn(*it);
ll[k]=min(ll[k],ll[*it]);}
else if(st[*it])
ll[k]=min(ll[k],ind[*it]);
}
if(ll[k]==ind[k]){
con.clear();
int w=0;
while(w!=k){
w=s.top();
con.push_back(w);
s.pop();
st[w]=false;
}
C.push_back(con);
}
}
int main(){
int x,y,i;
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y;
a[x].push_back(y);
}
for(i=1;i<=n;i++)st[i]=false;
for(i=1;i<=n;i++){
if(ind[i]==0)scn(i);
}
x=C.size();
fout<<x<<endl;
for(i=0;i<x;i++){
y=C[i].size();
for(int j=0;j<y;j++)
fout<<C[i][j]<<' ';
fout<<endl;
}
return 0;
}