Pagini recente » Cod sursa (job #132177) | Cod sursa (job #2378900) | Cod sursa (job #3238180) | Cod sursa (job #2349496) | Cod sursa (job #2527794)
#include <fstream>
#include <bitset>
#include <vector>
#include <deque>
#define dim 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,j,cnt,lvl,niv[dim],low[dim],x;
vector <int> l[dim];
bitset <dim> f;
vector <int> c[dim];
deque <int> q;
void dfs(int nod){
lvl++;
niv[nod]=lvl;
low[nod]=lvl;
q.push_back(nod);
f[nod]=1;
for(int i=0;i<l[nod].size();i++){
int vec=l[nod][i];
if(niv[vec]==0){
dfs(vec);
low[nod]=min(low[nod],low[vec]);
}else{
if(f[vec])
low[nod]=min(low[nod],niv[vec]);
}
}
if(low[nod]==niv[nod]){
cnt++;
do{
x=q.back();
c[cnt].push_back(x);
f[x]=0;
q.pop_back();
}while(x!=nod);
}
}
int main(){
fin>>n>>m;
for(;m;m--){
fin>>i>>j;
l[i].push_back(j);
}
for(i=1;i<=n;i++)
if(niv[i]==0)
dfs(i);
fout<<cnt<<"\n";
for(i=1;i<=cnt;i++,fout<<"\n")
for(j=0;j<c[i].size();j++)
fout<<c[i][j]<<" ";
return 0;
}