Cod sursa(job #1438189)

Utilizator tudor00Stoiean Tudor tudor00 Data 19 mai 2015 11:22:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int NMAX=100010;

int n,m,j,contor,a,b;
int marcat[NMAX];
vector<int> g[NMAX];

void dfs(int x)
{
    marcat[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        if(marcat[g[x][i]]==0) dfs(g[x][i]);
    }
}
int main()
{
    in>>n>>m;
    for(j=1;j<=m;j++)
    {
        in>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(j=1;j<=n;j++)
    {
        if(marcat[j]==0)
        {
            dfs(j);
            contor++;
        }
    }
    out<<contor;
    in.close();
    out.close();
    return 0;
}