Pagini recente » Cod sursa (job #3302444) | Cod sursa (job #1370194) | Cod sursa (job #3310244) | Cod sursa (job #1912983) | Cod sursa (job #2740728)
#include <stdio.h>
#include <stdlib.h>
int visited[100001];
int n, e;
int main()
{
FILE* f = fopen("dfs.in", "r");
fscanf(f, "%d %d", &n, &e);
int numberGraphs = 0, color = 0;
int x, y;
for (int i = 0; i < e; i++) {
fscanf(f, "%d %d", &x, &y);
if (!visited[x] && !visited[y]) {
numberGraphs++;
color++;
visited[x] = color;
visited[y] = color;
} else if (!visited[x])
visited[x] = visited[y];
else if (!visited[y])
visited[y] = visited[x];
else {
//to do
if (visited[x] != visited[y]) {
numberGraphs--;
int aux = visited[x];
for (int j = 1; j <= n; j++)
if (visited[j] == aux)
visited[j] = visited[y];
//to do parcurg si schimb culoarea
}
//else aceeasi culoare deci nimic
}
}
for (int i = 1; i <= n; i++)
if (!visited[i]) numberGraphs++;
FILE* g = fopen("dfs.out", "w");
fprintf(g, "%d", numberGraphs);
fclose(f);
fclose(g);
}
/*int n, e;
int visited[100001];
typedef struct edge {
int leftnode;
int rightnode;
} edge;
void dfs(int currentNode, int graphColor, edge* edges, int* visited)
{
if (!visited[currentNode]) {
visited[currentNode] = graphColor;
for (int i = 0; i < e; i++) {
if (edges[i].leftnode == currentNode)
dfs(edges[i].rightnode, graphColor, edges, visited);
if (edges[i].rightnode == currentNode)
dfs(edges[i].leftnode, graphColor, edges, visited);
}
}
}
int main()
{
FILE* f = fopen("dfs.in", "r");
fscanf(f, "%d %d", &n, &e);
int numberGraphs = 0;
edge* edges = (edge*)malloc(e * sizeof(edge));
for (int i = 0; i < e; i++)
fscanf(f, "%d %d", &edges[i].leftnode, &edges[i].rightnode);
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
numberGraphs++;
dfs(i, numberGraphs, edges, visited);
}
}
FILE* g = fopen("dfs.out", "w");
fprintf(g, "%d", numberGraphs);
fclose(f);
fclose(g);
/*for (int i = 1; i <= n; i++)
printf("%d ", visited[i]);
}
*/