Pagini recente » Cod sursa (job #2465337) | Cod sursa (job #1542829) | Cod sursa (job #2479110) | Cod sursa (job #2961743) | Cod sursa (job #2346491)
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire();
void afisare();
void DFSp(int nod);
void DFSm(int nod);
int N,M,cnt;
int viz[NMAX];
vector <int> g[NMAX],gt[NMAX],rez[NMAX];
vector <int> Q;
int main()
{
int i,j;
citire();
for(i=1; i<=N; i++)
if(!viz[i])
{
viz[i]=1;
DFSp(i);
}
for(i=1; i<=N; i++)
viz[i]=0;
cnt =0;
for(i=Q.size()-1; i>=0; i--)
if(!viz[Q[i]])
{
cnt++;
rez[cnt].push_back(Q[i]);
viz[Q[i]]=1;
DFSm(Q[i]);
}
afisare();
return 0;
}
void citire()
{
int i,ei,ef;
fin>>N>>M;
for(i=1; i<=M; i++)
{
fin>>ei>>ef;
g[ei].push_back(ef);
gt[ef].push_back(ei);
}
}
void DFSp(int nod)
{
vector <int>::iterator it;
for(it=g[nod].begin(); it!=g[nod].end(); it++)
if(!viz[*it])
{
viz[*it]=1;
DFSp(*it);
}
Q.push_back(nod);
}
void DFSm(int nod)
{
vector <int>::iterator it;
for(it=gt[nod].begin(); it!=gt[nod].end(); it++)
if(!viz[*it])
{
viz[*it]=1;
DFSm(*it);
rez[cnt].push_back(*it);
}
}
void afisare()
{
int i;
fout<<cnt<<'\n';
vector <int>::iterator it;
for(i=1; i<=cnt; i++)
{
for(it=rez[i].begin(); it!=rez[i].end(); it++)
fout<<*it<<' ';
fout<<'\n';
}
}