Pagini recente » Cod sursa (job #1945716) | Cod sursa (job #1635169) | Cod sursa (job #1612832) | Cod sursa (job #293964) | Cod sursa (job #1380224)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G[100005], stiva, CTC[100005];
int t_intrare[100005], t_minim[100005];
bool viz[100005];
void dfs(int nod, int k, int &nr)
{
int i;
viz[nod]=1;
t_intrare[nod]=t_minim[nod]=k;
stiva.push_back(nod);
for(i=0;i<G[nod].size();i++)
{if(viz[G[nod][i]]==0)
dfs(G[nod][i],k+1,nr);
if(t_minim[G[nod][i]]<t_minim[nod])
t_minim[nod]=t_minim[G[nod][i]];
}
if(t_minim[nod]==t_intrare[nod])
{
nr++;
while(stiva.back()!=nod)
{
CTC[nr].push_back(stiva.back());
stiva.pop_back();
}
CTC[nr].push_back(stiva.back());
stiva.pop_back();
}
}
int main()
{
int n,m,i,x,y,nr=0,j;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
G[x].push_back(y);
}
for(i=1;i<=n;i++)
if(viz[i]==0)
dfs(i,1,nr);
g<<nr<<'\n';
for(i=1;i<=nr;i++)
{
for(j=0;j<CTC[i].size();j++)
g<<CTC[i][j]<<' ';
g<<'\n';
}
return 0;
}