Pagini recente » Cod sursa (job #1969229) | Cod sursa (job #2772177) | Cod sursa (job #3135357) | Cod sursa (job #650506) | Cod sursa (job #2725018)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define NMAX 100005
vector <int> g[NMAX];
int i, m, n, a[NMAX], viz[NMAX], onStack[NMAX], id, low[NMAX], poz, x, y ,st[NMAX], vf, k, rasp[NMAX];
void dfs(int nod)
{
id++;
viz[nod]=low[nod]=id;
onStack[nod]=1;
vf++;
st[vf]=nod;
for(unsigned int i=0; i<g[nod].size(); i++)
{
int curr=g[nod][i];
if(!viz[curr])
dfs(curr);
if(onStack[curr])
low[nod]=min(low[nod],low[curr]);
}
if(low[nod]==viz[nod])
{
poz++;
while(st[vf+1]!=nod && vf>=0)
{
k++;
a[k]=st[vf];
low[st[vf]]=low[nod];
onStack[st[vf]]=0;
vf--;
}
rasp[poz]=k;
}
}
int main()
{
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>x>>y;
g[x].push_back(y);
}
id=0;
for(i=1; i<=n; i++)
{
if(viz[i]==0)
{
dfs(i);
}
}
fout<<poz<<'\n';
k=0;
for(i=1; i<=poz; i++)
{
while(k<rasp[i])
{
k++;
fout<<a[k]<<" ";
}
fout<<'\n';
}
return 0;
}