Pagini recente » Cod sursa (job #710093) | Cod sursa (job #2449467) | Cod sursa (job #2430956) | Cod sursa (job #2723275) | Cod sursa (job #2710858)
#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#define dim 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,j,low[dim],niv[dim],lvl,cnt;
vector <int> l[dim],c[dim];
bitset <dim> f; // tine minte nodurile din coada
deque <int> q;
void dfs(int nod){
q.push_back(nod);
f[nod]=1;
niv[nod]=low[nod]=++lvl;
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]==1)
low[nod]=min(low[nod],low[vec]);
}
if(low[nod]==niv[nod]){
cnt++;
int x;
do{
x=q.back();
q.pop_back();
f[x]=0;
c[cnt].push_back(x);
}while(x!=nod);
//sort(c.begin(),c.end());
}
return;
}
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;
}