Pagini recente » Cod sursa (job #17495) | Cod sursa (job #2134548) | Cod sursa (job #2836467) | Cod sursa (job #1694092) | Cod sursa (job #1291073)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
unsigned long n,m,nr,nrc;
vector<unsigned>A[100001],AT[100001],Solutii[100001];
vector<bool>viz(100001,0);
unsigned long postordine[100001],indice=0;
ofstream f1("ctc.out");
void DFS(unsigned long x)
{
viz[x]=1;
for (unsigned long i=1;i<=A[x].size()-1;i++)
if (!viz[A[x][i]]) DFS(A[x][i]);
postordine[++nr]=x;
}
void DFST(unsigned long x)
{
viz[x]=0;
Solutii[indice].push_back(x);
for (unsigned long i=1;i<=AT[x].size()-1;i++)
if (viz[AT[x][i]]) DFST(AT[x][i]);
}
void citire()
{
ifstream f("ctc.in");
f>>n>>m;
for (unsigned long i=1;i<=n;i++)
{
A[i].push_back(0);
AT[i].push_back(0);
}
for (unsigned long i=1;i<=m;i++)
{
unsigned long a,b;
f>>a>>b;
A[a].push_back(b);
AT[b].push_back(a);
}
}
int main()
{
citire();
for (unsigned long i=1;i<=n;i++)
if (!viz[i]) DFS(i);
for (unsigned long i=n;i>0;i--)
if (viz[postordine[i]])
{
indice++;
DFST(postordine[i]);
nrc++;
}
f1<<nrc<<"\n";
for (unsigned long i=1;i<=indice;i++)
{
for (unsigned long j=0;j<=Solutii[i].size()-1;j++)
f1<<Solutii[i][j]<<" ";
f1<<"\n";
}
return 0;
}