Cod sursa(job #1469420)

Utilizator adina0822Ciubotaru Adina-Maria adina0822 Data 8 august 2015 12:11:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
using namespace std;
#include <fstream>
#include <vector>

FILE *f=fopen ("dfs.in", "r");
FILE *g=fopen ("dfs.out", "w");

int n;
vector <int> G[100001];
int viz[100001];
int nrc;

void read();
void solve();
void write();
void dfs(int);



int main ()
{

  read();
  solve();
  write();



  return 0;
}

void read()
{
    int i,x,y,m;
    fscanf(f,"%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        fscanf(f,"%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

}

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

void write ()
{
    fprintf(g,"%d",nrc);
}

void dfs(int x)
{
    int i,y;
    viz[x]=1;
    vector <int> :: iterator it;
    for(it=G[x].begin(); it!=G[x].end(); it++)
    {
        y=*it;
        if(!viz[y])
         dfs(y);
    }
}