Pagini recente » Cod sursa (job #1879320) | Cod sursa (job #2986953) | Cod sursa (job #1521261) | Cod sursa (job #333370) | Cod sursa (job #2618728)
#include <stdio.h>
#include <vector>
typedef std::vector<int> Graph;
void dfs(Graph graph[], int nod, int viz[])
{
viz[nod] = 1;
for (int it = 0; it < graph[nod].size(); it++)
{
int i = graph[nod][it];
if (!viz[i])
dfs(graph, i, viz);
}
}
int main()
{
FILE *in = fopen("dfs.in", "r");
FILE *out = fopen("dfs.out", "w");
int n, m;
fscanf(in, "%d%d", &n, &m);
Graph *graph = new Graph[n];
for (int i = 0; i < m; i++)
{
int nod1, nod2;
fscanf(in, "%d%d", &nod1, &nod2);
nod1--;
nod2--;
graph[nod1].push_back(nod2);
graph[nod2].push_back(nod1);
}
int *viz = new int[n]();
int nr = 0;
for (int i = 0; i < n; i++)
{
if (!viz[i])
{
dfs(graph, i, viz);
nr++;
}
}
fprintf(out, "%d\n", nr);
delete viz;
delete[] graph;
fclose(in);
fclose(out);
return 0;
}