Cod sursa(job #2539176)

Utilizator razvan123vRazvan Vranceanu razvan123v Data 5 februarie 2020 18:40:31
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
//
//  main.cpp
//  dfs infoarena
//
//  Created by Razvan Vranceanu on 05/02/2020.
//  Copyright © 2020 Razvan Vranceanu. All rights reserved.
//

#include <fstream>
#define N 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m, viz[N];
struct nod{
    int x;
    nod *leg;
} *L[N];
void adauga(nod *&pp, int val)
{
    nod *p=new nod;
    p->x=val;
    p->leg=pp;
    pp=p;
}
void citire(int &n, int &m)
{
    f>>n>>m;
    int x, y;
    for(int i=1;i<=n;i++)
    {
        f>>x>>y;
        adauga(L[x], y);
        adauga(L[y], x);
    }
    f.close();
}
void DFS(int i)
{
    viz[i]=1;
    nod *p;
    for(p = L[i]; p; p = p -> leg)
        if(! viz[p -> x])
            DFS(p -> x);
}
int main() {
    citire(n, m);
    int nrcc=0;
    for(int i=1;i<=n;i++)
        if(!viz[i])
        {
            nrcc++;
            DFS(i);
        }
    g<<nrcc;
    return 0;
}