Cod sursa(job #247316)

Utilizator mihai.cuculiciCuculici Mihail mihai.cuculici Data 22 ianuarie 2009 19:48:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#include<vector>
using namespace std;
#define NMAX 100010
ifstream f ("dfs.in");
ofstream g ("dfs.out");
vector <int> A[NMAX];
int viz[NMAX], N, M, x, y, i, nr=0;
typedef struct nod* Nod;
struct nod
{
   int Key;
   Nod Next; 
};

Nod V[NMAX];

void add(Nod &dest, int val)   
{   
    Nod p;   
    p = new nod;   
    p->Key = val;   
    p->Next = dest;   
    dest = p;   
}   

void dfs(int x)
{
     viz[x]=1;
     Nod p;
     for(p=V[x];p;p=p->Next) if(!viz[p->Key]) dfs(p->Key);
}

int main()
{
    f>>N>>M;
    for(i=1;i<=M;i++) f>>x>>y, add(V[x], y), add(V[y], x);
    for(i=1;i<=N;i++) if(!viz[i]) dfs(i), nr++;
    g<<nr;
    g.close();
    return 0;
}