Pagini recente » Cod sursa (job #119657) | Cod sursa (job #407304) | Cod sursa (job #381173) | Cod sursa (job #2742181) | Cod sursa (job #1811677)
#include <stdio.h>
#include <vector>
#define MAX_N 100005
#define MAX_M 200005
using namespace std;
FILE* fin;
FILE* fout;
struct Member
{
vector<int> neighbours;
};
int n, m;
bool used[MAX_N] = { false };
Member nodes[MAX_N];
int result = 0;
void LoadFiles()
{
fin = fopen("dfs.in", "r");
fout = fopen("dfs.out", "w");
}
void Init()
{
LoadFiles();
}
void Read()
{
int e1, e2;
fscanf(fin, "%d %d", &n, &m);
for(int i=0;i<m;i++)
{
fscanf(fin, "%d %d", &e1, &e2);
e1--;
e2--;
nodes[e1].neighbours.push_back(e2);
nodes[e2].neighbours.push_back(e1);
}
}
void Dfs(int index)
{
used[index] = true;
int counts = nodes[index].neighbours.size();
int next;
for(int i=0;i<counts;i++)
{
next = nodes[index].neighbours[i];
if(!used[next])
{
Dfs(next);
}
}
}
void Solve()
{
for(int i=0;i<n;i++)
{
if(!used[i])
{
result++;
Dfs(i);
}
}
}
void Write()
{
fprintf(fout, "%d\n", result);
}
void CloseFiles()
{
fclose(fin);
fclose(fout);
}
void Terminate()
{
CloseFiles();
}
int main(void)
{
Init();
Read();
Solve();
Write();
Terminate();
return 0;
}