Cod sursa(job #2007206)

Utilizator andreistanStan Andrei andreistan Data 2 august 2017 11:17:10
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M;
bool a[1001][1001], viz[1001];

//DFS adancime

void citiregraf()
{
    f >> N >> M;
    while(M--)
    {
        int x, y;
        f >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}
/*
void afisareMatAdiacenta()
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
    cout << endl;
}
*/
void adancime(int x)
{
    int j, vf, cr, s[1001];
    vf = 1;
    s[vf] = x;
    viz[x] = 1;
    //cout << x << ' ';
    while(vf != 0)
    {
        cr = s[vf];
        int gasit = 0;
        for(j = 1; j <= N; j++)
            if(a[cr][j] == 1 && viz[j] == 0)
            {
                gasit = 1;
                break;
            }
        if(gasit)
        {
            //cout << j << ' ';
            s[++vf] = j;
            viz[j] = 1;
        }
        else vf--;
    }
    //cout << endl;
}

void componente()
{
    int i, compconex = 0;
    for(i = 1; i <= N; i++)
        viz[i] = 0;
    for(i = 1; i <= N; i++)
        if(viz[i] == 0)
        {
            adancime(i);
            compconex++;
        }
    g << compconex;
}

int main()
{
    citiregraf();
    //afisareMatAdiacenta();
    componente();
    return 0;
}