Cod sursa(job #2086908)

Utilizator KrosomAngelo Barbu Krosom Data 12 decembrie 2017 17:52:24
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#define DIM 1001

using namespace std;

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

int n, m, nrc;
int A[DIM][DIM], s[DIM];

void read()
{
    int i, j;
    f>>n>>m;
    while(f>>i>>j)
        A[i][j]=A[j][i]=1;
    f.close();
}

void DFS(int k)
{
    s[k]=nrc;
    for (int i=1; i<=n; i++)
        if (A[k][i]==1 && s[i]==0)
            DFS(i);
}

void solve()
{
    read();
    for (int i=1; i<=n; i++)
        if (!s[i])
        {
            nrc++;
            DFS(i);
        }
}

int main()
{
    read();
    solve();
    g<<nrc<<"\n";
    g.close();
    return 0;
}