Pagini recente » Cod sursa (job #1962924) | Cod sursa (job #791653) | Cod sursa (job #2073173) | Cod sursa (job #421982) | Cod sursa (job #1138609)
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
fstream f("ctc.in",ios::in);
fstream g("ctc.out",ios::out);
const long nmax=100005;
vector <long> a[nmax];
stack <long> s;
vector <long> tc[nmax];
long n,m,i,x,y,nrc,ind[nmax],link[nmax],index;
int viz[nmax],stiva[nmax];
void citire()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
a[x].push_back(y);
}
}
void nod(long nc)
{
long nc1;
ind[nc]=index;
link[nc]=index;
index++;
viz[nc]=1;
stiva[nc]=1;
s.push(nc);
for (vector<long>::iterator it=a[nc].begin();it!=a[nc].end();++it)
if (!viz[*it])
{
nod(*it);
if (link[nc]>link[*it]) link[nc]=link[*it];
}
else if (stiva[*it])
{
if (link[nc]>ind[*it]) link[nc]=ind[*it];
}
if (ind[nc]==link[nc])
{
nrc++;
do
{
nc1=s.top();
s.pop();
stiva[nc1]=0;
tc[nrc].push_back(nc1);
}
while (nc1!=nc);
}
}
void rezolvare()
{
memset(viz,0,sizeof(viz));
memset(stiva,0,sizeof(stiva));
index=1;
nrc=0;
for(i=1;i<=n;i++) if (!viz[i]) nod(i);
}
void afisare()
{
g<<nrc<<'\n';
for (i=1;i<=nrc;i++)
{
for (vector<long>::iterator it=tc[i].begin();it!=tc[i].end();++it) g<<*it<<" ";
g<<'\n';
}
}
int main()
{
citire();
rezolvare();
afisare();
f.close();g.close();
return 0;
}