Cod sursa(job #1987675)

Utilizator andr3i_kaabAndrei Ciineanu andr3i_kaab Data 31 mai 2017 17:40:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int /*a[1001][1001]*/ viz[100001], n, gr;
vector <int> a[100001];

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

void DF(int i)
{
  int j;
  viz[i]=gr;
  //for (j=1; j<=n; j++)
    //if (a[i][j]==1 && viz[j]==0) DF(j);
  for (j=0; j<a[i].size(); j++)
    if (viz[a[i][j]]==0) DF(a[i][j]);
}

int main()
{int m,i,x,y;
f>>n>>m;
for (i=1; i<=m; i++)
    {
   f>>x>>y;
   //a[x][y]=1; a[y][x]=1;
   a[x].push_back(y); a[y].push_back(x);
    }
for (i=1; i<=n; i++)
    if (viz[i]==0)
    {
        gr++;
        DF(i);
    }
    g<<gr<<"\n";
    // for (i=1; i<=n; i++)
    // cout<< viz[i];
/*for (j=1; j<=gr; j++)
{
   for (i=1; i<=n; i++)
    if (viz[i]==j) cout<<i<<" ";
   cout<<"\n";

}*/
    return 0;
}