Cod sursa(job #2209945)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 5 iunie 2018 09:55:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
vector <int> v[100001];
bool verif[100001];
void dfs(int i)
{
    int j;
    verif[i]=1;
    for(j=0;j<v[i].size();j++)
    {
        if(verif[v[i][j]]==0)
        dfs(v[i][j]);
    }
}
int main()
{
    int n,m,i,j,c=0;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        int a,b;
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
    {
        if(verif[i]==0)
        {
            dfs(i);
            c++;
        }
    }
    out<<c;
    return 0;
}