Pagini recente » Cod sursa (job #771450) | Borderou de evaluare (job #2830537) | Cod sursa (job #1275309) | Cod sursa (job #2715821) | Cod sursa (job #1250455)
#include <cstdio>
#define NMAX 100100
using namespace std;
FILE*fout=fopen("ctc.out", "w");
char ctc[NMAX], viz[NMAX];
int postord[NMAX], lgpord;
int n, m, nr_ctc;
struct nod
{int inf;
struct nod *urm;
};
typedef struct nod *Lista;
Lista A[NMAX], AT[NMAX], CTC[NMAX];
void inserare(Lista&, Lista, int);
void citire();
void DFS1(int);
void DFS2(int);
void rez();
int main()
{
citire();
rez();
return 0;
}
void citire()
{
FILE*fin=fopen("ctc.in", "r");
fscanf(fin, "%d %d", &n, &m);
int i, x, y;
for (i=1; i<=m; ++i)
{
fscanf(fin, "%d %d", &x, &y);
//am arc de la x la y
inserare (A[x], NULL, y);
//in graful transpus, am arc de la y la x
inserare (AT[y], NULL, x);
}
fclose(fin);
return;
}
void rez()
{
int i; Lista q;
for (i=1; i<=n; ++i)
if (!viz[i])//nu l-am vizitat
DFS1(i);
//resetez vectorul viz
for (i=1; i<=n; ++i)
viz[i]=0;
for (i=lgpord; i>0; --i)
if (!ctc[postord[i]])//nu se afla in nicio componenta conexa
{
++nr_ctc;
DFS2 (postord[i]);
}
//afisez componentele conexe
fprintf(fout, "%d\n", nr_ctc);
for (i=1; i<=nr_ctc; ++i)
{
for (q=CTC[i]; q; q=q->urm)
fprintf(fout, "%d ", q->inf);
fprintf(fout, "\n");
}
fclose(fout);
return;
}
void DFS1(int vf)//construiesc vectorul postordine
{
viz[vf]=1;//l-am vizitat
Lista q;
for (q=A[vf]; q; q=q->urm)
if (!viz[q->inf])
DFS1 (q->inf);
postord[++lgpord]=vf;
}
void DFS2 (int vf)
{
ctc[vf]=1;
//retin varful in componenta conexa curenta
inserare (CTC[nr_ctc], NULL, vf);
Lista q;
for (q=AT[vf]; q; q=q->urm)
if (!ctc[q->inf])
DFS2(q->inf);
}
void inserare (Lista &prim, Lista p, int x)
{
Lista q;
q=new nod;
q->inf=x;
if (p)
{
q->urm=p->urm;
p->urm=q;
}
else
{
q->urm=prim;
prim=q;
}
return;
}