Cod sursa(job #1991305)

Utilizator lorena1999Marginean Lorena lorena1999 Data 16 iunie 2017 10:58:01
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, m, a[20000][20000], x, y;

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

void citire()
    {
        f>>n>>m;
        for(int i=1; i<=m; i++)
        {
            f>>x>>y;
            a[x][y]=a[y][x]=1;
        }
    }

int viz[200000];

void dfs(int vf, int nrc)
    {
        viz[vf]=1;
        for(int i=1; i<=n; i++)
        {
            if(viz[i]==0 && a[i][vf]==1)
            {
                dfs(i, nrc);
            }
        }
    }

int main()
    {
        citire();
        int nrc=1;
        int c=0;
        for(int i=1; i<=n; i++)
        {
            if(viz[i]==0)
            {
                dfs(i, nrc);
                nrc++;
                c++;
            }
        }
        g<<c;
    }