Cod sursa(job #749802)

Utilizator alexalbu95Albu Alexandru alexalbu95 Data 18 mai 2012 20:29:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
// DFS - alocare dinamica
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
const int maxn=100001;
int U[maxn], ans, n, m;
struct point{
    int info;
    point *urm;
}*G[100001];

void add(int x, int y)
{
    point *p;
    p=new point;
    p->info=y;
    p->urm=G[x];
    G[x]=p;
}

void citire()
{
    int i, j;
    f>>n>>m;
    for(int k=1; k<=m; ++k)
    {
        f>>i>>j;
        add(i, j);
        add(j, i);
    }
}

void dfs(int nod)
{
    point *p;

    U[nod] = 1;
    for(p=G[nod]; p!=NULL; p=p->urm)
        if(!U[p->info])
            dfs(p->info);
}

int main()
{
    citire();
    for(int i=1; i<=n; ++i)
        if(!U[i])
        {
            ++ans;
            dfs(i);
        }
    g<<ans<<"\n";
}