Cod sursa(job #2379764)

Utilizator AndrulianDin Iulian Andrulian Data 14 martie 2019 00:05:13
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <limits>
#include <cstddef>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int nmax=10005;
struct lista
{
    int vecin[nmax];
    int nr;
};
lista nod[nmax];
int n,m;
bool viz[nmax];
void DFS(int x)
{
    viz[x]=1;
    for(int i=1; i<=nod[x].nr; i++)
        if(!viz[nod[x].vecin[i]])
            DFS(nod[x].vecin[i]);
}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x1,x2;
        fin>>x1>>x2;
        nod[x1].nr++;
        nod[x1].vecin[nod[x1].nr]=x2;
        nod[x2].nr++;
        nod[x2].vecin[nod[x2].nr]=x1;
    }
    int nr=0;
    for(int i=1; i<=n; i++)
    {
        if(!viz[i])
        {
            nr++;
            DFS(i);
        }
    }
    fout<<nr;
}