Cod sursa(job #1752263)

Utilizator GinguIonutGinguIonut GinguIonut Data 3 septembrie 2016 13:22:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#define nMax 100001

using namespace std;

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

int n, m, Sol;
int viz[nMax];
vector<int> G[nMax];
void read()
{
    int a, b;
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
}

void dfs(int node)
{
    viz[node]=1;

    for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
    {
        int fiu=*it;

        if(viz[fiu]==0)
            dfs(fiu);
    }
}

void solve()
{
    for(int i=1; i<=n; i++)
        if(viz[i]==0)
        {
            dfs(i);
            Sol++;
        }
}

void write()
{
    fout<<Sol;
}

int main()
{
    read();
    solve();
    write();
}