Cod sursa(job #1833784)

Utilizator sahleancosminSahlean Cosmin sahleancosmin Data 23 decembrie 2016 09:49:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,lista[200001],urm[200001],inc[100001],sf,nr;
bool vf[100001];
void dfs(int i)
{
    vf[i]=true;
    for(int j=inc[i];j;j=urm[j])
    {
        if(!vf[lista[j]])
        {
            dfs(lista[j]);
        }
    }
}
int main()
{
   f>>n>>m;
   int x,y;
   for(int i=1;i<=m;i++)
   {
       f>>x>>y;
       lista[++sf]=y;
       urm[sf]=inc[x];
       inc[x]=sf;
       lista[++sf]=x;
       urm[sf]=inc[y];
       inc[y]=sf;
   }
   for(int i=1;i<=n;i++)
        if(!vf[i])
        {
            dfs(i);
            nr++;
        }
        g<<nr;
    return 0;
}