Pagini recente » Cod sursa (job #1682592) | Cod sursa (job #872748) | Cod sursa (job #1501318) | Cod sursa (job #1604097) | Cod sursa (job #710728)
Cod sursa(job #710728)
#include<fstream>
using namespace std;
#define lung 100001
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod{int val;
nod *next;
};
nod *v[lung],*transp[lung],*rasp[lung];
bool pluss[lung],minu[lung],frecv[lung];
inline void bf1(int x)
{nod *q=v[x];
if (q)
if (!pluss[q->val])
while(q)
{ pluss[q->val] = true;
bf1(q->val);
q = q -> next;
}
}
inline void bf2(int x)
{nod *q=transp[x];
if (q)
if (!minu[q->val])
while(q)
{ minu[q->val] = true;
bf2(q->val);
q = q -> next;
}
}
int main()
{nod *q;
int i,n,m,a,b,nr=0,j;
fin >> n >> m;
for (i=1;i<=m;++i)
{ fin >> a >> b;
q = new nod;
q -> next = v[a];
q -> val = b;
v[a] = q;
q = new nod;
q -> next = transp[b];
q -> val = a;
transp[b] = q;
}
for (i=1;i<=n;++i)
if (!frecv[i])
{ pluss[i] = true;
minu[i] = true;
bf1(i);
bf2(i);
++nr;
for (j=1;j<=n;++j)
if (pluss[j] && minu[j])
{ q = new nod;
q -> val = j;
q -> next = rasp[nr];
rasp[nr] = q;
frecv[j] = true;
}
for (j=1;j<=n;++j)
pluss[j] = minu[i] = false;
}
fout << nr << '\n';
for (i=1;i<=nr;++i)
{ q = rasp[i];
while (q)
{ fout << q->val << " ";
q = q->next;
}
fout << '\n';
}
return 0;
}