Pagini recente » Cod sursa (job #2847105) | Cod sursa (job #2250985) | Cod sursa (job #1017847) | Cod sursa (job #949274) | Cod sursa (job #2675401)
///infoarena.ro/problema/ctc
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define O 500000
using namespace std;
vector<int> G[O],GT[O],R[O];
int viz[O];
int n,m,nr;
stack <int> s;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire()
{
fin>>n>>m;
int x, y;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFS1(int z)
{
viz[z]=1;
for(int i=0;i<G[z].size();i++)
{
int Vecin=G[z][i];
if(viz[Vecin]==0)
DFS1(Vecin);
}
s.push(z);
}
void DFS2(int z)
{
viz[z]=2;
R[nr].push_back(z);
for(int i=0;i<GT[z].size();i++)
{
int Vecin=GT[z][i];
if(viz[Vecin]==1)
DFS2(Vecin);
}
}
int main()
{
citire();
for(int i=1;i<=n;i++)
if(viz[i]==0)
DFS1(i);
while(!s.empty())
{
int x=s.top();
if(viz[x]==1)
{
nr++;
DFS2(x);
}
s.pop();
}
fout<<nr<<endl;
for(int i=1;i<=nr;i++)
{
for(int j=0;j<R[i].size();j++)
fout<<R[i][j]<<" ";
fout<<endl;
}
return 0;
}