Pagini recente » Cod sursa (job #2377555) | Cod sursa (job #3266729) | Cod sursa (job #2163128) | Cod sursa (job #350109) | Cod sursa (job #412274)
Cod sursa(job #412274)
#include <stdio.h>
#include <stack>
#define infile "ctc.in"
#define outfile "ctc.out"
#define NMAX 100005
using namespace std;
typedef struct snod{int x;snod *nxt;}*L;
L G[NMAX],GT[NMAX],CMP[NMAX];
stack <int> stiva;
int vizitat[NMAX],N,M,NCMP;
void add(int,int,L*),citire(),rezolvare(),afisare();
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire();
rezolvare();
afisare();
}
void afisare()
{
printf("%d\n",NCMP);
for(int i=1;i<=NCMP;i++)
{
for(L p=CMP[i];p;p=p->nxt)
printf("%d ",p->x);
printf("\n");
}
}
//rezolvarea problemei - parcurgerile DF
void DF1(int nod)
{
vizitat[nod]=1;
for(L p=G[nod];p;p=p->nxt)
if(!vizitat[p->x])DF1(p->x);
stiva.push(nod);
}
void DF2(int nod,int k)
{
//printf("%d ",nod);
add(k,nod,CMP);
vizitat[nod]=1;
for(L p=GT[nod];p;p=p->nxt)
if(!vizitat[p->x])DF2(p->x,k);
}
void rezolvare()
{
//prima parcurgere
int i;
for(i=1;i<=N;i++)
if(!vizitat[i])DF1(i);
//reinitializam vectorul vizitat[] cu 0
for(i=1;i<=N;i++)vizitat[i]=0;
//a doua parcurgere - pe graful transpus
for(i=1;!stiva.empty();stiva.pop())
{
int nod=stiva.top();
if(!vizitat[nod])
DF2(nod,i++);
}
NCMP=i-1;
}
//citirea din fisier
void citire()
{
int i,s,d;
scanf("%d %d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d %d",&s,&d);
add(s,d,G);
add(d,s,GT);
}
}
void add(int a,int b,L *g)
{
L aux=new snod;
aux->x=b;
aux->nxt=g[a];
g[a]=aux;
}