Pagini recente » Cod sursa (job #3154854) | Cod sursa (job #1197454) | Cod sursa (job #689403) | Cod sursa (job #136193) | Cod sursa (job #1529451)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack<int> S;
vector<int> V[100001],G[100001];
int n,m,i,viz[100001],da[100001],mic[100001],nr[100001],numar,k,j;
void ctc(int nod)
{
int vecin;
nr[nod] = mic [nod] = numar;
numar++;
da[nod] = 1;
S.push(nod); viz[nod]=1;
for (size_t i=0; i<G[nod].size(); i++)
{
vecin = G[nod][i];
if (viz[vecin]==0)
{ctc(vecin); if(mic[nod]>mic[vecin]) mic[nod] = mic[vecin];}
else if (da[vecin]) { if(mic[nod]>nr[vecin]) mic[nod] = nr[vecin];}
}
if (mic[nod] == nr[nod])
{
int nn; k++;
do {
V[k].push_back(nn = S.top());
S.pop();
da[nn] = 0;
}
while (nn != nod);
}
}
int main()
{
int a,b;
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>a>>b;
G[a].push_back(b);
}
for (i=1;i<=n;i++)
if (!viz[i]) ctc(i);
g<<k<<"\n";
for (i=1;i<=k;i++)
{
for(size_t j=0; j<V[i].size(); j++)
g<<V[i][j]<<" ";
g<<"\n";
}
return 0;
}