Cod sursa(job #1098658)

Utilizator dropsdrop source drops Data 4 februarie 2014 23:33:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
/* 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);
}