Cod sursa(job #1024808)

Utilizator dragosaioaneiAioanei Dragos dragosaioanei Data 9 noiembrie 2013 09:11:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#define IN "dfs.in"
#define OUT "dfs.out"
#define NMAX 100005

int viz[NMAX],n,m,componente;
vector<int> graf[NMAX];
stack<int> stiva;

void citire();
void rezolvare();
void afisare();
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}

void citire()
{
    FILE * fin=fopen(IN,"r");

    int i,x,y;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    fclose(fin);
}

void rezolvare()
{
    int contor,element,z,y,i;
    for(contor=1;contor<=n;contor++)
    {
        if(viz[contor]==0)
        {
            componente++;
            stiva.push(contor);
            viz[contor]=1;
            while(!stiva.empty())
            {
                element=stiva.top();
                y=-1;
                for(i=0;i<graf[element].size();i++)
                {
                    z=graf[element][i];
                    if(viz[z]==0)
                    {
                        viz[z]=1;
                        stiva.push(z);
                        y=1;
                        break;
                    }
                }
                if(y==-1)
                    stiva.pop();
            }
        }
    }
}

void afisare()
{
    FILE * fout=fopen(OUT,"w");

    fprintf(fout,"%d\n",componente);

    fclose(fout);
}