Cod sursa(job #1216857)

Utilizator ValeraShulghin Valera Valera Data 5 august 2014 22:46:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int n,m,a,b,viz[100001],componente;
vector <int> graf[100001];

void DFS(int x)
{
    viz[x]=1;
    for(int i=0;i<graf[x].size();i++)
    {
        if (viz[graf[x][i]]==0)
            DFS(graf[x][i]);
    }
}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    for(i=1;i<=n;i++)
        if (viz[i]==0)
        {
            componente++;
            DFS(i);
        }

    g<<componente;
    return 0;
}