Cod sursa(job #2512717)

Utilizator hellhathnofuryAilincai Andrei hellhathnofury Data 21 decembrie 2019 14:14:06
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M, cc,x, y;
bool b[100000];
struct Nod{ int info;
            Nod* leg;
          }*L[100000], *p;
void ad(int x, int y)
{ p=new Nod;
  p->info=x;
  p->leg=L[y];
  L[y]=p;
  p=new Nod;
  p->info=y;
  p->leg=L[x];
  L[x]=p;
}
void dfs(int i)
{
  b[i]=1;
  Nod *p=L[i];
  while(p) { if(b[p->info]==0)
                dfs(p->info);
             p=p->leg;
           }
}
int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++){ f>>x>>y;
                           ad(x,y);
                         }
    for(int i=1;i<=N;i++)
        if(b[i]==0) { b[i]=1;
                      cc++;
                      dfs(i);
                    }
        g<<cc;
    return 0;
}