Pagini recente » Cod sursa (job #187866) | Rating Leonardo Da Vinci (LeoDavinci17) | Profil alboi | Cod sursa (job #376502) | Cod sursa (job #2169969)
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 100005
#define mmax 200005
using namespace std;
fstream f1("ctc.in", ios::in);
fstream f2("ctc.out", ios::out);
int n, m, nrcomp, viz[nmax], l[nmax], nrl;
vector <int> v[nmax], vt[nmax], comp[nmax];
///pui nodurile in lsta l de la stanga la dreapta (dfs, pui nodul care nu mai are vecini nezivitati)
///parcurgi lista de la dreapta la stanga si din fiecare nod, nodurile in care ajungi fac parte din aceeasi componenta conexa cu acesta
void citire()
{
int i, x, y;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
v[x].push_back(y);
vt[y].push_back(x);
}
}
void dfs(int nod)
{
viz[nod]=1;
for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
if(!viz[*it])
dfs(*it);
nrl++; l[nrl]=nod;
}
void dfs_t(int nod)
{
viz[nod]=1;
for(auto it=vt[nod].begin(); it!=vt[nod].end(); ++it)
if(!viz[*it])
{
dfs_t(*it);
comp[nrcomp].push_back(*it);
}
}
void solve()
{
int i;
for(i=1; i<=n; i++) viz[i]=0;
for(i=nrl; i>=1; i--)
if(!viz[l[i]])
{
nrcomp++;
comp[nrcomp].push_back(l[i]);
dfs_t(l[i]);
}
}
void afis()
{
int i;
f2<<nrcomp<<"\n";
for(i=1; i<=nrcomp; i++)
{
sort(comp[i].begin(), comp[i].end());
for(auto it=comp[i].begin(); it!=comp[i].end(); ++it)
f2<<*it<<' ';
f2<<"\n";
}
}
int main()
{
citire();
for(int i=1; i<=n; i++)
if(!viz[i]) dfs(i);
solve();
afis();
return 0;
}