Cod sursa(job #1922938)

Utilizator HoriaDruliacHoria Druliac HoriaDruliac Data 10 martie 2017 19:42:40
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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, i,j, x, z[1005][1005] ;
int a, b, ans;
bool ok[VAL];
//vector<int> v[VAL];

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

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

    return 0;
}