Cod sursa(job #1707493)

Utilizator dominiciorgandaDominic Iorganda dominiciorganda Data 25 mai 2016 11:41:09
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int>f[100001];
bool g[100001];
int k,i,m,x,j,ct;
void DFS(int x)
{
    int k,i,m;
    g[x]=1;
    for(k=0;k<f[x].size();k++)
    {
        if(!g[f[x][k]])
        {
            g[f[x][k]]=1;
            DFS(f[x][k]);
        }
    }
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%d%d",&i,&j);
        f[i].push_back(j);
    }
    for(k=1;k<=x;k++)
    {
        if(!g[k])
        {
            ct++;
            DFS(k);
        }
    }
    printf("%d\n",ct);
    return 0;
}