Cod sursa(job #396065)

Utilizator curcubeuPop Simina curcubeu Data 14 februarie 2010 14:09:35
Problema Sortare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <vector>

using namespace std;

vector <int> A[100001];
int viz[100001],n,m,k,nr_componente_conexe;
void citeste_graf()
{    int x,y,i;
     ifstream f("dfs.in");
     
     f>>n>>m;

     
     for(i=1;i<=m;i++)
     {
                      f>>x>>y;
                      A[x].push_back(y);
                      A[y].push_back(x);
                      }
     f.close();
     }
     
void dfs(int nod)
   { viz[nod]=1;
             int nr_vecini,i;
             nr_vecini=A[nod].size();
             for(i=0;i<nr_vecini;i++)
                if (viz[A[nod][i]]==0) 
                        dfs(A[nod][i]);
}
             

void afisare()
{
     ofstream g("dfs.out");
 
    g<<nr_componente_conexe;
           
      g.close();
      }


int main()
{int i;
    citeste_graf();
    for(i=1;i<=n;i++)
      if (viz[i]==0) {nr_componente_conexe++;
                        dfs(i);
                       }
    
    afisare();
    return 0;
}