Pagini recente » Cod sursa (job #2942446) | Cod sursa (job #2233181) | Cod sursa (job #3262114) | Cod sursa (job #1123545) | Cod sursa (job #1098658)
/* Componente conexe - DFS */
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 100001
vector<int> Edge[MAX];
int N, M, X, Y, K;
bool Was[MAX];
void DFS(int X)
{
int Y;
Was[X] = 1;
for (int i = 0; i < Edge[X].size(); i++)
{
Y = Edge[X][i];
if (!Was[Y])
{
DFS(Y);
}
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; i++)
{
scanf("%d %d", &X, &Y);
Edge[X].push_back(Y);
Edge[Y].push_back(X);
}
for (int i = 1; i <= N; i++)
if (!Was[i])
{
K++;
DFS(i);
}
printf("%d\n", K);
}