Cod sursa(job #2086028)

Utilizator BazagazealOancea Eduard Bazagazeal Data 11 decembrie 2017 10:15:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.84 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node
{
    int data;
    struct _Node *next;
}Node;
Node *p[100001];
int viz[100001];
void adaugare_dupa(Node *p,int valoare)
{
    Node *q=(Node*)malloc(sizeof(Node));
    q->next=p->next;
    q->data=valoare;
    p->next=q;
}

void show(Node *p, FILE *g)
{
    Node *q=p->next;
    if(q==p)
        fprintf(g,"0\n");
        else
        {
            while(q!=p)
            {
                fprintf(g,"%d ", q->data);
                q=q->next;
            }
        fprintf(g,"\n");
        }
}
void edges_to_matrix()
{
    FILE *f=fopen("grafuri.in", "r");
    FILE *g=fopen("grafuri.out", "w");
    int n,m,M[6][6],x,y,i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            M[i][j]=0;
    fscanf(f,"%d %d", &n, &m);
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d%d", &x, &y);
        M[x][y]=M[y][x]=1;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            fprintf(g,"%d ", M[i][j]);
        fprintf(g,"\n");
    }
}

void DFS(Node *p[],int nod)
{
    Node *q;
    viz[nod]=1;
    for(q=p[nod]->next;q!=p[nod];q=q->next)
        if(viz[q->data]==0)
            DFS(p,q->data);

}
int main()
{
    FILE *f=fopen("dfs.in", "r");
    FILE *g=fopen("dfs.out", "w");
    int n,m,x,y,i,j,nr=1;
    Node *p[100001];
    fscanf(f,"%d %d", &n, &m);
    for(i=1;i<=n;i++)
    {
        p[i]=(Node*)malloc(sizeof(Node));
        p[i]->next=p[i];
        p[i]->data=0;
    }
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d%d", &x ,&y);
        adaugare_dupa(p[x],y);
        adaugare_dupa(p[y],x);
    }
   // for(i=1;i<=n;i++)
    //    show(p[i],g);
    DFS(p,1);
    for(i=2;i<=n;i++)
        if(viz[i]==0)
        {
            DFS(p,i);
            nr++;
        }
    fprintf(g,"%d", nr);
    return 0;
}