Cod sursa(job #3200359)

Utilizator danutbodbodnariuc danut danutbod Data 4 februarie 2024 14:00:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include<algorithm>
#include <vector>
#define NMAX 100003
using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");
int k,n, m, u,p, s,i,j,x,y,ncc;
vector <int> a[NMAX];
vector <int> viz(NMAX,0);
void DFS(int nod)
{
    int  i,t;
    viz[nod]=1;
    t=a[nod].size();
    for(i=0; i<t; i++)
        if(viz[a[nod][i]]==0)DFS(a[nod][i]);
}
int main()
{
    fi>>n>>m;
    for(i=1; i<=m; i++)
    {
        fi>>x>>y;
        a[x].push_back(y);   //pune in lista nodului x nodul y
        a[y].push_back(x);   //pune in lista nodului y nodul x
    }
    //
    for(i=1;i<=n;i++)
    if(viz[i]==0){ncc++; DFS(i);}
    fo<<ncc;
    fo.close();
    fi.close();
    return 0;
}