Pagini recente » Borderou de evaluare (job #851245) | Borderou de evaluare (job #2321822) | Cod sursa (job #485011) | Cod sursa (job #799886) | Cod sursa (job #2509501)
#define NMAX 100005
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, nr, nrC, nrviz;
int viz[NMAX];
vector<int> G[NMAX], Gt[NMAX];
vector<int> afis[NMAX];
stack<int> parc;
void read()
{
int x, y;
f>>n>>m;
for(int i=1; i<=m; ++i)
{
f>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void DFS(int nod)
{
nrviz++;
viz[nod] = -1;
for(auto &v:G[nod])
if(viz[v] == 0)
DFS(v);
parc.push(nod);
}
void DFSt(int nod, int nr)
{
viz[nod] = nr;
for(auto &v:Gt[nod])
if(viz[v] <= 0)
DFSt(v, nr);
afis[nr].push_back(nod);
}
void afisare()
{
g<<nr<<"\n";
for(int i=1; i<=nr; ++i)
{
for(auto &v:afis[i])
g<<v<<" ";
g<<'\n';
}
}
int main()
{
read();
while(nrviz < n)
{
for(int i=1; i<=n; ++i)
if(viz[i] == 0)
DFS(i);
}
while(!parc.empty())
{
int vf = parc.top();
if(viz[vf] > 0)
parc.pop();
else{
nr++;
DFSt(vf, nr);
}
}
afisare();
return 0;
}