Cod sursa(job #1200003)

Utilizator breahnadavidBreahna David breahnadavid Data 21 iunie 2014 15:15:11
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<vector>
#include<fstream>
#define maxn 100005

using namespace std;

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

vector <int> t[maxn];
int i,j,n,m,nod[maxn],coada[maxn],comp,sf_coada;

void dfs(int k)
        {
        coada[1]=k;
        sf_coada=1;
        nod[k]=1;
        for(int i=1;i<=sf_coada;i++)
                for(int j=0;j<t[coada[i]].size();j++)
                if(nod[t[coada[i]][j]]==0)
                        {
                        coada[++sf_coada]=t[coada[i]][j];
                        nod[t[coada[i]][j]]=1;
                        }
        comp++;
        }

int main()
{
f>>n>>m;
while(m>0)
        {
        f>>i>>j;
        t[i].push_back(j);
        t[j].push_back(j);
        m--;
        }
comp=0;
for(i=1;i<=n;i++)if(nod[i]==0)dfs(i);
g<<comp;
g.close();
return 0;
}