Pagini recente » Cod sursa (job #2492681) | Cod sursa (job #2103410) | Cod sursa (job #1493507) | Cod sursa (job #800889) | Cod sursa (job #710791)
Cod sursa(job #710791)
#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];
int cd[lung],tot;
inline void bf1(int x)
{nod *q=v[x];
if (q)
while(q)
{ if (!pluss[q->val])
{ pluss[q->val] = true;
bf1(q->val);
}
q = q -> next;
}
}
inline void bf2(int x)
{nod *q=transp[x];
if (q)
while(q)
{ if (!minu[q->val])
{ minu[q->val] = true;
cd[++tot]=q->val;
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;
cd[++tot]=i;
bf1(i);
bf2(i);
++nr;
for (j=1;j<=tot;++j)
if (pluss[cd[j]] && minu[cd[j]])
{ q = new nod;
q -> val = cd[j];
q -> next = rasp[nr];
rasp[nr] = q;
frecv[cd[j]] = true;
}
for (j=1;j<=tot;++j)
pluss[cd[j]] = minu[cd[j]] = false;
tot = 0;
}
fout << nr << '\n';
for (i=1;i<=nr;++i)
{ q = rasp[i];
while (q)
{ fout << q->val << " ";
q = q->next;
}
fout << '\n';
}
return 0;
}