Cod sursa(job #1984800)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 25 mai 2017 23:48:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<bits/stdc++.h>

#define maxNumberOfNodes 400100

int numberOfNodes;
int numberOfEdges;
int sourceNode;
int ind;
int node1;
int node2;
bool isVisited[ maxNumberOfNodes ];
int D[maxNumberOfNodes];
int left = 1;
int right = 1;
int headQueue;
int solution;
struct Nodes
{
        int data;
        struct Nodes *next;
};

Nodes *addiacencyList[ maxNumberOfNodes ];

void add_to_list_forward(int node1, int node2)
{
        Nodes *head = new Nodes;
        head -> data = node2;
        head -> next = addiacencyList[node1];
        addiacencyList[node1] = head;


        struct Nodes *head2 = new Nodes;
        head2 -> data = node1;
        head2 -> next = addiacencyList[node2];
        addiacencyList[node2] = head2;
}

void DFS(int nod)
{
        isVisited[nod] = true;

        Nodes *listIterator;

        for(listIterator = addiacencyList[nod]; listIterator != NULL; listIterator = listIterator -> next)
        {
                if(isVisited[ listIterator -> data ] == false)
                {
                        DFS(listIterator -> data);
                }
        }
}

int main()
{
        FILE *fin = fopen("dfs.in", "r");
        FILE *fout = fopen("dfs.out", "w");


        fscanf(fin, "%d %d", &numberOfNodes, &numberOfEdges);

        for(ind = 1; ind <= numberOfEdges; ind ++)
        {
                fscanf(fin, "%d %d", &node1, &node2);
                add_to_list_forward(node1, node2);
        }

        for(ind = 1; ind <= numberOfNodes; ind ++)
        {
                if(isVisited[ind] == false)
                {
                        DFS(ind);
                        solution ++;
                }
        }

        fprintf(fout, "%d", solution);


        return 0;
}