Cod sursa(job #2469443)

Utilizator bogdan_modoleaBogdan Modolea bogdan_modolea Data 7 octombrie 2019 11:54:07
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;

string text="dfs";

ifstream fin(text+".in");
ofstream fout(text+".out");
typedef long long ll;

int n,m,ans;
int a[NMAX/10][NMAX/10],vizitat[NMAX];

void dfs(int x){
    int i;
    for(i=1;i<=n;i++){
        if(a[x][i]==1){
            if(!vizitat[i]){
                vizitat[i]=1;
                dfs(i);
            }
        }

    }

}

int main()
{
    int x,y,i;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        a[x][y]=1;
    }
    for(i=1;i<=n;i++){
        if(!vizitat[i]){
            dfs(i); ans++;
        }
    }
    fout<<ans;
    return 0;
}