Pagini recente » Cod sursa (job #2075108) | Cod sursa (job #2370159) | Cod sursa (job #2466004) | Cod sursa (job #2069995) | Cod sursa (job #1984800)
#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;
}