Cod sursa(job #2086917)

Utilizator KrosomAngelo Barbu Krosom Data 12 decembrie 2017 17:59:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#define DIM 100001

using namespace std;

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

int n, m, nrc;
int T[2][4*DIM], Start[DIM], s[DIM];

void read()
{
    int i, j, k=0;
    f>>n>>m;
    while (f>>i>>j)
    {
        k++;
        T[0][k]=j;
        T[1][k]=Start[i];
        Start[i]=k;
        k++;
        T[0][k]=i;
        T[1][k]=Start[j];
        Start[j]=k;
    }
    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);*/
    int p;
    p=Start[k];
    s[k]=nrc;
    while (p)
    {
        if (s[T[0][p]]==0)
            DFS(T[0][p]);
        p=T[1][p];
    }
}

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;
}