Cod sursa(job #1507530)

Utilizator IulianBogIulian Bogdanovici IulianBog Data 21 octombrie 2015 18:41:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX=100000;
vector <int>g[NMAX+5];

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

int cc;
int viz[NMAX+5];

void dfs(int u)
{
    int i;
    viz[u]=cc;
    for(i=0;i<(int)g[u].size();++i)
    {
        int v=g[u][i];
        if(!viz[v])
            dfs(v);
    }
}
int main()
{
    int n,m,u,v,i;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(i=1;i<=n;++i)
    {
        if(!viz[i])
        {
            cc++;
            dfs(i);
        }
    }
    out<<cc;
    return 0;
}