Cod sursa(job #384658)

Utilizator UnOrdinaryVyper Boy UnOrdinary Data 20 ianuarie 2010 17:38:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream.h>
#define MAXN 100000

int a[MAXN][MAXN],n,m,viz[MAXN];
void dfs(int k)
{
    int i;
    viz[k]=1;
    for(i=0;i<n;i++)
    {
        if(viz[i]==0&&a[k][i])
        {
            dfs(i);
        }
    }
}

void main()
{
    int i,j,c,b,ncomp;
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    fin>>n>>m;
    for (i=0;i<m;i++)
    {
        fin>>c>>b;
        c--;b--;
        a[c][b]=1;
        a[b][c]=1;
    }
    ncomp=0;
    for (i=0;i<n;i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            ncomp++;
        }
    }
    fout<<ncomp<<endl;
}