Cod sursa(job #397771)

Utilizator UnOrdinaryVyper Boy UnOrdinary Data 17 februarie 2010 14:16:56
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#define MAXN 100000
using namespace std;

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;
}