Pagini recente » Cod sursa (job #2396542) | Cod sursa (job #1720322) | Cod sursa (job #2427713) | Cod sursa (job #2903507) | Cod sursa (job #475611)
Cod sursa(job #475611)
// Componente tare conexe.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "stdio.h"
FILE *f=fopen("ctc.in", "r");
FILE *g=fopen("ctc.out", "w");
typedef struct nod
{
int x;
struct nod *adr;
};
typedef struct dflo
{
int dfn;
int low;
};
nod *l[100001];
nod *ll[100001];
int n, m;
dflo v[100001];
int viz[100001];
int nr, nrc;
int st[100001];
int aux[100001];
int s;
void add(int x, int y)
{
nod *p=new nod;
p->x=y;
p->adr=l[x];
l[x]=p;
}
void add2(int x, int y)
{
nod *p=new nod;
p->x=y;
p->adr=ll[x];
ll[x]=p;
}
void read()
{
fscanf(f, "%d%d", &n, &m);
for (int i=1; i<=m; ++i)
{
int x, y;
fscanf(f, "%d%d", &x, &y);
add(x, y);
}
}
int minim(int x, int y)
{
if (x<y) return x;
return y;
}
void afis(int x)
{
++nrc;
while(st[s+1]!=x)
{
aux[st[s]]=-1;
add2(nrc, st[s--]);
}
}
void dfs(int x)
{
aux[x]=1;
st[++s]=x;
v[x].dfn=v[x].low=++nr;
viz[x]=1;
nod *p=l[x];
while (p!=NULL)
{
if (!viz[p->x])
{
dfs(p->x);
v[x].low=minim(v[x].low, v[p->x].low);
}
else
{
if (aux[p->x]==1)
v[x].low=minim(v[x].low, v[p->x].dfn);
}
p=p->adr;
}
if (v[x].low==v[x].dfn)
{
afis(x);
}
}
void program()
{
for (int j=1; j<=n; ++j)
if (!viz[j])
{
nr=0;
s=0;
dfs(j);
}
}
int main()
{
read();
program();
fprintf(g, "%d\n", nrc);
for (int i=1; i<=nrc; ++i)
{
nod *p=ll[i];
while (p!=NULL)
{
fprintf(g, "%d ", p->x);
p=p->adr;
}
fprintf(g, "\n");
}
fclose(f);
fclose(g);
return 0;
}