Cod sursa(job #972550)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 12 iulie 2013 01:57:17
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");

queue <int> q;
stack <int> s;

struct nod{
    int v;
    nod *next;
};
typedef nod *lista;

int n,m,used[100001];
lista lv[100001];

void readGRAPH()
{
    int i,a,b;
    lista p;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d%d",&a,&b);
        p=new nod;p->v=a;p->next=lv[b];lv[b]=p;
        p=new nod;p->v=b;p->next=lv[a];lv[a]=p;
    }
}
void BFS(int k)
{
    q.push(k);
    used[k]=1;
    lista p;
    while(!q.empty())
    {
        for(p=lv[q.front()];p;p=p->next)
            if(!used[p->v])used[p->v]=1,q.push(p->v);
        q.pop();
    }
}
void DFS(int k)
{
    s.push(k);
    used[k]=1;
    lista p;
    while(!s.empty())
    {
        for(p=lv[s.top()];p;p=p->next)
            if(!used[p->v])used[p->v]=1,s.push(p->v);
        s.pop();
    }
}
int main()
{
    readGRAPH();
    int conex=0;
    for(int i=1;i<=n;++i)
        if(!used[i])
        {
            ++conex;
            //BFS(i);
            DFS(i);
        }
    fprintf(g,"%d",conex);
    return 0;
}