Cod sursa(job #2512719)

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