Pagini recente » Cod sursa (job #2063143) | Cod sursa (job #2905288) | Cod sursa (job #175447) | Cod sursa (job #2875312) | Cod sursa (job #2199626)
#include <stdio.h>
const int MAX_N = 100000;
const int MAX_M = 200000;
struct list;
struct Node
{
int id;
list *to;
Node *next;
};
struct list
{
int id;
Node *p;
}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].p;
lists_pointers[x].p = &edges[n_edges];
n_edges++;
}
char was[MAX_N];
void dfs(list *l)
{
if(l != NULL)
{
Node *x = l->p;
while(x != NULL)
{
/*printf("here %d\n", x->to->id);*/
if(was[x->to->id] == false)
/*printf("%d\n", x->to->id),*/ dfs(x->to);
was[x->to->id] = true;
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);
}
for(int i = 0; i < n; i++)
lists_pointers[i].id = i;
r = 0;
for(int i = 0; i < n; i++)
{
if(was[i] == false)
{
was[i] = true;
//printf("----\n%d\n", i);
dfs(&lists_pointers[i]);
r++;
}
}
fprintf(fout, "%d\n", r);
fclose(fin);
fclose(fout);
return 0;
}