Pagini recente » Cod sursa (job #2175748) | Cod sursa (job #2392941) | Cod sursa (job #1294391) | Cod sursa (job #2155780) | Cod sursa (job #2891620)
#include <stdio.h>
#include <stdlib.h>
typedef struct edge
{
int leftNode;
int rightNode;
} edge;
typedef struct graphEdges
{
edge *edges;
int numNodes;
int numEdges;
int S;
} graphEdges;
int lmax;
graphEdges readGraphEdgeList(const char *fileName)
{
graphEdges graph;
graph.numEdges = 0;
graph.edges = NULL;
FILE *f = fopen(fileName, "r");
if (f == NULL)
return graph;
if (!feof(f))
{
fscanf(f, "%d", &(graph.numNodes));
fscanf(f, "%d", &(graph.numEdges));
fscanf(f, "%d", &(graph.S));
}
graph.edges = (edge *)malloc((graph.numEdges + 1) * sizeof(edge));
int k = 1;
while (!feof(f))
{
fscanf(f, "%d %d", &(graph.edges[k].leftNode), &(graph.edges[k].rightNode));
k++;
}
fclose(f);
return graph;
}
void BFS(graphEdges graph, int target, FILE *f)
{
for (int i = 1; i <= graph.numEdges; i++)
{
if (graph.edges[i].rightNode == target && graph.edges[i].leftNode == graph.S)
{
if (target == graph.numNodes)
{
fprintf(f, "%d", lmax + 1);
}
else
fprintf(f, "%d ", lmax + 1);
lmax = 0;
return;
}
if (graph.edges[i].rightNode == target)
{
target = graph.edges[i].leftNode;
lmax++;
i = i - 2;
}
}
fprintf(f, " %d ", -1);
}
int main(int argc, char *argv[])
{
graphEdges graph = readGraphEdgeList("bfs.in");
FILE *f = fopen("bfs.out", "w");
for (int i = 1; i <= graph.numNodes; i++)
{
if (i == graph.S)
fprintf(f, "%d ", 0);
else
BFS(graph, i, f);
}
fclose(f);
return 0;
}