Pagini recente » Cod sursa (job #53778) | Cod sursa (job #286395) | Cod sursa (job #360626) | Cod sursa (job #1349512) | Cod sursa (job #765426)
Cod sursa(job #765426)
#include <fstream>
#include <vector>
using namespace std;
ifstream F("ctc.in");
ofstream G("ctc.out");
#define Nmax 100011
#define Mmax 200011
vector<int> First[Nmax],Second[Nmax];
vector<int> Sol[Nmax];
int Stiva[Nmax],Size;
int Used[Nmax],Mark[Nmax];
int N,M,Co;
void DFF(int Nod)
{
Used[Nod]=1;
int Stop=First[Nod].size();
for (int i=0;i<Stop;++i)
if ( !Used[First[Nod][i]] )
DFF( First[Nod][i] );
Stiva[++Size]=Nod;
}
void DFS(int Nod, int Value)
{
Mark[Nod] = Value;
int Stop=Second[Nod].size();
for (int i = 0; i < Stop; ++i)
if ( Mark[ Second[Nod][i]] == 0 )
DFS( Second[Nod][i], Value);
}
int main()
{
F>>N>>M;
for (int i=1;i<=M;++i)
{
int x,y;
F>>x>>y;
First[x].push_back(y);
Second[y].push_back(x);
}
for (int i=1;i<=N;++i)
if ( !Used[i] )
DFF(i);
for ( ;Size; Stiva[Size--]=0 )
if ( Mark[ Stiva[Size] ] == 0 )
DFS(Stiva[Size],++Co);
for (int i=1;i<=N;++i)
Sol[Mark[i]].push_back(i);
G<<Co<<"\n";
for (int i=1;i<=Co;++i)
{
for (unsigned int j=0;j<Sol[i].size();++j)
G<<Sol[i][j]<<" ";
G<<"\n";
}
}