Pagini recente » Cod sursa (job #208778) | Cod sursa (job #1682705) | Cod sursa (job #1425822) | Cod sursa (job #2713108) | Cod sursa (job #396675)
Cod sursa(job #396675)
# include <fstream>
# include <cstdio>
using namespace std;
struct nod {
int info;
nod *next;};
nod *g[100004], *gt[100003], *ctc[100003];
int n, m, final[100003], timp, v[100003], vt[100003], nrc;
void add (int i, int j)
{
nod *q=new nod;
q->info=j;
q->next=g[i];
g[i]=q;
}
void addt (int i, int j)
{
nod *q=new nod;
q->info=j;
q->next=gt[i];
gt[i]=q;
}
void read ()
{
ifstream fin ("ctc.in");
fin>>n>>m;
for (int i=1;i<=m;i++)
{
int x, y;
fin>>x>>y;
add (x, y);
addt (y, x);
}
}
void afis ()
{
freopen ("ctc.out", "w", stdout);
printf("%d\n", nrc);
for (int i=1;i<=nrc;i++)
{
nod *p=ctc[i];
while (p)
{
printf("%d ", p->info);
p=p->next;
}
printf("\n");
}
}
void dfs (int k)
{
v[k]=1;
for (nod *p=g[k];p;p=p->next)
if (!v[p->info])
dfs(p->info);
final[++timp]=k;
}
void dfst (int k, int nrc)
{
vt[k]=nrc;
nod *q=new nod;
q->info=k;
q->next=ctc[nrc];
ctc[nrc]=q;
for (nod *p=gt[k];p;p=p->next)
if (!vt[p->info])
dfst(p->info, nrc);
}
void kosaraju ()
{
for (int i=1;i<=n;i++)
if(v[i]==0)
dfs(i);
for (int i=timp;i;--i)
if (vt[final[i]]==0)
{
++nrc;
dfst(final[i], nrc);
}
}
int main ()
{
read ();
kosaraju ();
afis ();
return 0;
}