Cod sursa(job #1922948)

Utilizator HoriaDruliacHoria Druliac HoriaDruliac Data 10 martie 2017 19:50:29
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <cstdio>
//#include <vector>
#define VAL 100005

using namespace std;       /// Varianta 1 ... de 50 pct cu Matrice de adiacenta .

int N, M, z[1005][1005] ;
int a, b, ans;
bool ok[VAL];
//vector<int> v[VAL];

void citire ()
{
    int i;
    scanf("%d %d",&N,&M);
    for(i=1; i<=M; i++)
    {
        scanf("%d %d ",&a,&b);
        z[a][b]=1;
        z[b][a]=1;
    }
}
void dfs(int b)
{
    int i;
    ok[b]=1;
    for(i=1; i<=N; i++)
        if(!ok[i] && z[b][i])
            dfs(i);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    citire();
    int i;
    for(i=1; i<=N; i++)
        if(!ok[i])
        {
            ++ans;
            dfs(i);
        }
    printf("%d\n",ans);

    return 0;
}