Cod sursa(job #2326636)

Utilizator adrian_dumitrescu_fmi_uvtIoan - Adrian Dumitrescu adrian_dumitrescu_fmi_uvt Data 23 ianuarie 2019 19:25:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
using namespace std;
ofstream out("dfs.out");
ifstream in("dfs.in");
ifstream file("dfs.in");

long v[100001], cd[100001], v1[100001], com[100001], componente;
long *c[100001];
long var, n;
void dfs(int nod)
{
    componente++;
    long f = 1, l = 1;
    com[var] = componente;
    cd[f] = nod;
    while(f <= l)
    {
        for(long i = 1; i <= v[cd[f]]; i++)
        {
            if(com[c[cd[f]][i]] != componente)
            {
                com[c[cd[f]][i]] = componente;
                l++;
                cd[l] = c[cd[f]][i];
            }
        }
        f++;
    }
}
int main()
{

    long a, b, m;
    in>>n>>m;
    for(var = 1; var <= m; var++)
    {
        in>>a>>b;
        v[a]++;
        v[b]++;
    }
    in.close();
    for(var = 1; var <= n; var++)
        c[var] = new long[v[var] + 1];


    file>>n>>m;
    for(var = 1; var <= m; var++)
    {
        file>>a>>b;
        c[a][v1[a] + 1] = b;
        v1[a]++;
        c[b][v1[b] + 1] = a;
        v1[b]++;
    }
    file.close();


    for(var = 1; var <= n; var++)
        if(v[var] == 0)
            com[var]= ++componente;
        else if(com[var] == 0)
            dfs(var);

    out<<componente<<"\n";

    out.close();
    return 0;
}