Pagini recente » Cod sursa (job #656889) | Cod sursa (job #1375455) | Cod sursa (job #2421483) | Cod sursa (job #632900) | Cod sursa (job #2199615)
#include <stdio.h>
const int MAX_N = 100000;
const int MAX_M = 200000;
struct Node
{
int to;
int id;
Node *next;
};
Node* lists_pointers[MAX_N];
Node connections[MAX_M * 2];
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(lists_pointers[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);
x --;
y --;
connections[2 * i] = {x, y, lists_pointers[y]};
connections[2 * i + 1] = {y, x, lists_pointers[x]};
lists_pointers[y] = &connections[2 * i];
lists_pointers[x] = &connections[2 * i + 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;
}