Pagini recente » Cod sursa (job #1290973) | Cod sursa (job #1062561) | Cod sursa (job #2061849) | Cod sursa (job #2683982) | Cod sursa (job #2199618)
#include <stdio.h>
const int MAX_N = 100000;
const int MAX_M = 200000;
struct Node
{
int id;
Node **to;
Node *next;
};
Node* lists_pointers[MAX_N];
Node edges[MAX_M * 2];
int n_edges;
void add_edge(int x, int y)
{
edges[n_edges].id = x;
edges[n_edges].to = &lists_pointers[y];
edges[n_edges].next = lists_pointers[x];
lists_pointers[x] = &edges[n_edges];
n_edges++;
}
char was[MAX_N];
void dfs(Node *root)
{
if(root != NULL && was[root->id] != false)
{
was[root->id] = true;
Node *x = root;
while(x != NULL)
{
dfs(*(x->to));
x = x->next;
}
}
}
int main()
{
FILE *fin = fopen("dfs.in", "r"),
*fout = fopen("dfs.out", "w");
int n, m;
int r;
fscanf(fin, "%d %d", &n, &m);
for (int i = 0; i < m; i++)
{
int x, y;
fscanf(fin, "%d %d", &x, &y);
add_edge(x - 1, y - 1);
add_edge(y - 1, x - 1);
}
r = 0;
for(int i = 0; i < n; i++)
{
if(was[i] == false)
{
dfs(lists_pointers[i]);
r++;
}
}
fprintf(fout, "%d\n", r);
fclose(fin);
fclose(fout);
return 0;
}