Cod sursa(job #2654522)

Utilizator razvan1403razvan razvan1403 Data 1 octombrie 2020 13:33:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> adj[100001];
void addEdge(vector<int> adj[], int u ,int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

bool beenThere[100001];
void DFS(int start_node)
{
    beenThere[start_node] = true;
    for(unsigned int i = 0;i< adj[start_node].size();i++)
    {
        int Next = adj[start_node][i];
        if(!beenThere[Next])
        {
            DFS(Next);
        }
    }
}

int main()
{
    long long n,m;
    
    fin>>n>>m;
    int i;
    int x,y;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        addEdge(adj,x,y);
    }
    int answer = 0;
    for(int i=1;i<=n;i++)
    {
        if(!beenThere[i])
        {
            answer = answer + 1;
            DFS(i);
        }
    }
    fout<<answer;
    fin.close();
    fout.close();
    return 0;
}