Cod sursa(job #1354894)

Utilizator RaileanuCristian Raileanu Raileanu Data 22 februarie 2015 10:13:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>

using namespace std;
ifstream f1("dfs.in");
ofstream f2("dfs.out");
#define N 100006
struct nod
        {
            int val, next;
        };
nod lst[3*N];

int n,m, first[N], last[N], sel[N], nrn ;

void dfs(int nod)
{
    sel[nod]=1;
    for (int i=  first[nod] ; i ; i= lst[i].next  )
        if ( !sel[ lst[i].val ] )
            dfs( lst[i].val );
}

void add_vecin(int nod, int v)
{
    if ( !first[nod] )
        {
            lst[++nrn].val= v;
            first[nod]=last[nod]=nrn;
            return;
        }

    lst[ ++nrn ].val= v;
    lst[ last[nod] ].next= nrn;
    last[nod]=nrn;
}

int main()
{
    int i, x, y, nr_componente=0;

    f1>>n>>m;
    for (i=1; i<=m; i++)
        {
            f1>>x>>y;
            add_vecin(x,y);
            add_vecin(y,x);
        }

    for (i=1; i<=n; i++)
        if ( !sel[i] )
            {
                nr_componente++;
                dfs(i);
            }

    f2<<nr_componente;
    f2.close();
    return 0;
}