Pagini recente » Cod sursa (job #2186702) | Cod sursa (job #132231) | Cod sursa (job #2154197) | Cod sursa (job #1503318) | Cod sursa (job #2537898)
#include <fstream>
#include <vector>
#include <bitset>
#include <iostream>
#define dim 100005
#include <deque>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int g,low[dim],niv[dim],ctc,n,m,x,y,i,j;
bitset<dim> IQ;
deque<int> q;
vector <int> L[dim],C[dim];
void dfs(int nod)
{
g++;
low[nod]=g;
niv[nod]=g;
IQ[nod]=1;
q.push_back(nod);
for(int i=0; i<L[nod].size(); i++)
{
int vecin=L[nod][i];
if(niv[vecin]==0){
dfs(vecin);
low[nod]=min(low[nod],low[vecin]);
}else if(IQ[nod]==1){
low[nod]=min(low[nod],low[vecin]);
}
}
if(low[nod]==niv[nod]){
ctc++;
do{
C[ctc].push_back(q.back());
IQ[q.back()]=0;
q.pop_back();
}while(q.back()!=nod);
C[ctc].push_back(q.back());
IQ[q.back()]=0;
//cout<<q.back()<<" ";
q.pop_back();
}
}
int main()
{
fin>>n>>m;
for(; m--;)
{
fin>>x>>y;
L[x].push_back(y);
}
for(i=1; i<=n; i++)
{
if(!niv[i])
{
dfs(i);
}
}
fout<<ctc<<"\n";
for(i=1;i<=ctc;i++){
for(j=0;j<C[i].size();j++)
fout<<C[i][j]<<" ";
fout<<"\n";
}
}