Cod sursa(job #209856)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 25 septembrie 2008 09:04:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
//dfs care merge excelent si e facut de marius si mircea, care si-au intrat deja in mana si o sa faca FSA in 2 minute in curand

#include <cstdio>
#include <fstream>
#include <stack>
#define MAX 100001

using namespace std;

ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

int v,x,y,m,n;
int viz[MAX];

struct nod
{
    int nr;
    nod*urm;
};

nod *g[MAX];
stack <int> s;

void baga(int x, int y)
{
    nod *q=new nod;
    q->nr=y;
    q->urm=g[x];
    g[x]=q;
}
 void citire()
 {
     int a,b;
     fin>>n>>m;
     for (int i=0;i<=n;i++)
         g[i]=NULL;

     for (int i=0;i<m;i++)
     {
         fin>>a>>b;
         baga(a,b);
         baga(b,a);
     }
     memset(viz,0,sizeof(viz));
 }
void adauga(int v2)
{
    nod *x=g[v2];
    while(x)
    {
        if(viz[x->nr]==0)
        {
            s.push(x->nr);
            viz[x->nr]=1;
        }
        x=x->urm;
    }
}

void dfs(int v)
{
    viz[v]=1;
    s.push(v);
    while(!s.empty())
    {
        int v2=s.top();
       // printf("%d ",v2);
        s.pop();
        adauga(v2);
    }
}

int main()
{
    citire();
    int nr=0;
    for (int i=1;i<=n;i++)
    if (viz[i]==0)
    {
            dfs(i);
            nr++;
    }
    fout<<nr;
    return 0;
}