Cod sursa(job #914572)

Utilizator BeniaminMarcu Beniamin Beniamin Data 14 martie 2013 11:49:09
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<cstdio>
using namespace std;
void afisare( int n, int a[][20000])
{
    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
            cout << a[i][j] << " ";
        cout << "\n";
    }
}

void init_a (int n, int a[][200000])
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            a[i][j] = 0;
}
void conex ( int x ,int n, int a[][200000], int viz[])
{
    viz[x] = 1;
    int i;
    for(i = 0 ; i < n; i++)
        if(a[i][x] == 1 && viz[i] == 0)   conex(i,n,a,viz);
}
int main()
{
    int i, j, n,m,x ,y, nr = 0, a[200000][200000], viz[200000];
    ifstream fin("dfs.in");
    fin >> n >> m;
    init_a(n,a);
    for(i = 0; i < n; i++)  viz[i] = 0;
    for(j = 0; j < m; j++)
    {
        fin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    afisare(n,a);
    for(i = 0; i < n; i++)
    {
        if(viz[i] == 0)
        {
            nr++;
            conex(i,n, a,viz);
        }
    }
    cout << nr;
    return 0;
}