Cod sursa(job #1433809)

Utilizator petrenoxxPietreanu Andrei petrenoxx Data 9 mai 2015 21:29:34
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
int a[20001][20001], viz[20001], n, m, i, j, cod[20001], inc, sf, e;

int main()
{
    in >> n >> m;
    for(i=1; i<=n; i++)
    {
        in >> inc >> sf;
        a[inc][sf]=a[sf][inc]=1;
    }
    inc=1;
    sf=1;

    for(i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            j++;
            viz[i]=j;
            inc++;
            sf=inc;
            cod[inc]=i;
            while(inc<=sf)
            {
                inc++;
                for(e=1; e<=n; e++)
                {
                    if(viz[e]==0&&a[e][cod[inc-1]]==1)
                    {
                        sf++;
                        viz[e]=j;
                        cod[sf]=e;
                    }
                }
            }
        }
    }
    out << j;
    return 0;
}