Cod sursa(job #1010876)

Utilizator shagarthAladin shagarth Data 15 octombrie 2013 20:55:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
 
using namespace std;
 
ifstream f("dfs.in");
ofstream g("dfs.out");
 
const int NMAX=100005;
int n,m,used[NMAX],count;
 
typedef struct nod
{
    int x;
    nod *urm;
}*pNod;
pNod v[NMAX];
 
void add (pNod &dest, int val)
{
    pNod p;
    p=new nod;
    p->x=val;
    p->urm=dest;
    dest=p;
}
 
void read ()
{
    f>>n>>m;
    for (int i=1, nod1, nod2; i<=m; i++)
    {
        f>>nod1>>nod2;
        add (v[nod1],nod2);
        add (v[nod2],nod1);
    }
}
 
void DFS (int punct)
{
    pNod p;
    used[punct]=1;
    for (p=v[punct]; p!=NULL; p=p->urm)
        if (!used[p->x])
            DFS (p->x);
}
 
 
int main ()
{
    read ();
    for (int i=1; i<=n; i++)
    {
        if (!used[i])
        {
            count++;
            DFS(i);
        }
    }
    g<<count;
 
    f.close();
    g.close();
    return 0;
}