Cod sursa(job #2098123)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 2 ianuarie 2018 13:56:46
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <iostream>
#include <fstream>
#define nmax 10005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,a[nmax][nmax],viz[nmax],nc=0;
void dfs(int x, int mark)
{
    viz[x]=mark;
    for(int i =1; i <= n ; i ++)
        if(a[x][i] && !viz[i])
        dfs(i,mark);

}
int main()
{
     int x,y;
       fin>>n>>m;
       for(int i =1; i <= m ; i ++)
       {
           fin>>x>>y;
           a[x][y]=a[y][x]=1;
       }
       for(int i=1; i <= n ; i++)
         if(!viz[i])
       {
           nc++;
           dfs(i,nc);
       }
       fout<<nc;
    return 0;
}