Cod sursa(job #1493653)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 29 septembrie 2015 19:07:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;

#define N 100005
#define M 200005

ifstream in("dfs.in");
ofstream out("dfs.out");

int lst[N], vf[2 * M], urm[2 * M];
int n, m, nr;
int stiva[N], nstiva;
bool ok[N];

int nrcomp;

int main()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        vf[++nr] = y;
        urm[nr] = lst[x];
        lst[x] = nr;
        vf[++nr] = x;
        urm[nr] = lst[y];
        lst[y] = nr;
    }

    for(int i = 1; i <= n; i++)
        if(ok[i] == 0)
        {
            nrcomp++;
            stiva[++nstiva] = i;
            while(nstiva)
            {
                int x = stiva[nstiva--];
                ok[x] = 1;

                for(int j = lst[x]; j; j = urm[j])
                {
                    int y = vf[j];
                    if(!ok[y])
                        stiva[++nstiva] = y;
                }
            }
        }

    out << nrcomp;
    return 0;
}