Pagini recente » Istoria paginii runda/dinamica_ii/clasament | Cod sursa (job #2294153) | Cod sursa (job #1817835) | Cod sursa (job #835130) | Cod sursa (job #1648268)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> L[100009], H[100009];
vector <int> sol[100009];
int N, M, nrsol, top, st[100009];
bool viz[100009];
void Citire()
{
int x, y, i;
fin >> N >> M;
for (i=1; i<=M; i++)
{
fin >> x >> y;
L[x].push_back(y);
H[y].push_back(x);
}
}
void DFS(int k)
{
int i, j;
viz[k] = 1;
for (j=0; j<L[k].size(); j++)
{
i = L[k][j];
if (!viz[i]) DFS(i);
}
st[++top] = k;
}
void DFS2(int k)
{
int i, j;
viz[k] = 1;
for (j=0; j<H[k].size(); j++)
{
i = H[k][j];
if (!viz[i]) DFS2(i);
}
sol[nrsol].push_back(k);
}
void Rezolva()
{
int i, j, nod;
top = 0;
for (i=1; i<=N; i++)
if (!viz[i]) DFS(i);
for (i=1; i<=N; i++)
viz[i] = 0;
while (top > 0)
{
nod = st[top--];
if (!viz[nod])
{
nrsol++;
DFS2(nod);
}
}
}
void Afisare()
{
int i, j;
fout << nrsol << "\n";
for (i=1; i<=nrsol; i++)
{
for (j=0; j<sol[i].size(); j++)
fout << sol[i][j] << " ";
fout << "\n";
}
}
int main ()
{
Citire();
Rezolva();
Afisare();
fin.close();
fout.close();
return 0;
}