Cod sursa(job #1727021)

Utilizator mirupetPetcan Miruna mirupet Data 9 iulie 2016 18:29:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#include<vector>
#define NMax 100002
using namespace std;

FILE *fin = freopen("dfs.in", "r", stdin);
FILE *fout = freopen("dfs.out", "w", stdout);

int N, M, X, Y;
int sol;
bool mark[NMax];
vector < int > v[NMax];

void DFS(int A)
{
    vector < int > :: iterator it;
    mark[A] = 1;

    for (it = v[A].begin(); it != v[A].end(); it++)
        if (!mark[*it])
            DFS(*it);
}
int main()
    {
        scanf("%d%d", &N, &M);

        for (int i = 1, X, Y; i <= M; i++)
        {
            scanf("%d%d", &X, &Y);
            v[X].push_back(Y);
            v[Y].push_back(X);
        }

        for (int i = 1; i <= N; i++)
            if (!mark[i])
            {
                DFS(i);
                sol++;
            }

        printf("%d", sol);
    }