Pagini recente » Cod sursa (job #1972417) | Cod sursa (job #120454) | Cod sursa (job #2089745) | Cod sursa (job #347641) | Cod sursa (job #2478449)
#include <fstream>
using namespace std;
int * A[100005], * AT[100005], viz[100005], postordine[100005], nr, * comp_conexe[100005], nr_comp;
void DFS(int x)
{
viz[x] = 1;
for (int i = 1; i <= A[x][0]; ++i)
if (!viz[A[x][i]])
DFS(A[x][i]);
postordine[++nr] = x;
}
void DFST(int x)
{
viz[x] = 0;
++comp_conexe[nr_comp][0];
comp_conexe[nr_comp] = (int *) realloc(comp_conexe[nr_comp], (comp_conexe[nr_comp][0] + 1) * sizeof(int));
comp_conexe[nr_comp][comp_conexe[nr_comp][0]] = x;
for (int i = 1; i <= AT[x][0]; ++i)
if (viz[AT[x][i]])
DFST(AT[x][i]);
}
int main()
{
ifstream fin("apm.in");
ofstream fout("apm.out");
int varfuri, muchii, i, j;
fin >> varfuri >> muchii;
for (i = 1; i <= varfuri; ++i)
{
A[i] = (int *) realloc(A[i], sizeof(int)), A[i][0] = 0;
AT[i] = (int *) realloc(AT[i], sizeof(int)), AT[i][0] = 0;
comp_conexe[i] = (int *) realloc(comp_conexe[i], sizeof(int)), comp_conexe[i][0] = 0;
}
for (i = 1; i <= muchii; ++i)
{
int v1, v2;
fin >> v1 >> v2;
++A[v1][0];
A[v1] = (int *) realloc(A[v1], (A[v1][0] + 1) * sizeof(int));
A[v1][A[v1][0]] = v2;
++AT[v2][0];
AT[v2] = (int *) realloc(AT[v2], (AT[v2][0] + 1) * sizeof(int));
AT[v2][AT[v2][0]] = v1;
}
for (i = 1; i <= varfuri; ++i)
if (!viz[i])
DFS(i);
for (i = varfuri; i >= 1; --i)
if (viz[postordine[i]])
{
++nr_comp;
DFST(postordine[i]);
}
fout << nr_comp << "\n";
for (i = 1; i <= nr_comp; ++i)
{
for (j = 1; j <= comp_conexe[i][0]; ++j)
fout << comp_conexe[i][j] << ' ';
fout << "\n";
}
}