Cod sursa(job #2478364)

Utilizator E1goBack Andrei-Gheorghe E1go Data 21 octombrie 2019 22:41:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct nod{int info;
           nod *urm, *ult;} *v[100001];
vector <int> viz;
int n, k;

void dfs( int x )
{
    nod *p;
    viz[x] = k;
    for(p = v[x]; p != NULL; p = p -> urm)
        {
            if(viz[p->info] == 0)
                dfs(p->info);
        }
}

int main()
{
    int m, a, b;
    fin >> n >> m;
    while( m-- )
    {
        fin >> a >> b;
        if(v[a] == NULL)
        {
            v[a] = new nod;
            v[a] -> urm = NULL;
            v[a] -> info = b;
            v[a] -> ult = v[a];
        }
        else
        {
          nod *p;
          p = new nod;
          p -> urm = NULL;
          p -> info = b;
          v[a] -> ult -> urm = p;
          v[a] -> ult = p;
        }

        if(v[b] == NULL)
        {
            v[b] = new nod;
            v[b] -> urm = NULL;
            v[b] -> info = a;
            v[b] -> ult = v[b];
        }
        else
        {
          nod *p;
          p = new nod;
          p -> urm = NULL;
          p -> info = a;
          v[b] -> ult -> urm = p;
          v[b] -> ult = p;
        }
    }

    viz.resize(n+1);
    for(int i=1; i<=n; i++)
    if(viz[i] == 0)
    {
        k++;
        if(viz[i] == 0)
            dfs(i);
    }

    fout<<k;

    return 0;
}