Pagini recente » Cod sursa (job #316066) | Cod sursa (job #2721053) | Cod sursa (job #295400) | Cod sursa (job #751813) | Cod sursa (job #1840709)
#include <fstream>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
struct nod
{
int inf;
nod *urm;
};
nod *p[100001], *u[100001], *x[100001], *y[100001];
int n, m, nr, s[100001], pred[100001];
void cit()
{
int i, j, k;
fin >> n >> m;
nod *q;
for (k=1; k<=m; k++)
{
fin >> i >> j;
if (p[i] == 0)
{
q = new nod;
q->inf = j;
q->urm = 0;
p[i] = q;
u[i] = q;
}
else
{
q = new nod;
q->inf = j;
q->urm = 0;
u[i]->urm = q;
u[i] = q;
}
if (x[j] == 0)
{
q = new nod;
q->inf = i;
q->urm = 0;
x[j] = q;
y[j] = q;
}
else
{
q = new nod;
q->inf = i;
q->urm = 0;
y[j]->urm = q;
y[j] = q;
}
}
}
void adancimes(int k)
{
nod *q;
s[k] = nr;
q = new nod;
q = p[k];
while (q != 0)
{
if (s[q->inf] == 0)
adancimes(q->inf);
q = q->urm;
}
}
void adancimep(int k)
{
nod *q;
pred[k] = nr;
q = new nod;
q = x[k];
while (q != 0)
{
if (pred[q->inf] == 0)
adancimep(q->inf);
q = q->urm;
}
}
int main()
{
cit();
int i, j;
for (i=1; i<=n; i++)
{
if (s[i] == 0)
{
nr++;
adancimes(i);
adancimep(i);
for (j=1; j<=n; j++)
if (s[j] == 0 || pred[j] == 0)
{
s[j] = 0;
pred[j] = 0;
}
}
}
fout << nr << '\n';
for (i=1; i<=nr; i++){
for (j=1; j<=n; j++)
if (s[j] == i)
fout << j <<" ";
fout << '\n';
}
return 0;
}