Cod sursa(job #1390977)

Utilizator cristi_pocCristi Porf cristi_poc Data 17 martie 2015 15:17:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int i,j,n,m,s,a,b,now,z,p,d[100010];
vector <int> v[100010];
queue <int> q;
int main()
{   f>>n>>m;
    for(i=1;i<=m;i++) {f>>a>>b; v[a].push_back(b); v[b].push_back(a);}
    for(j=1;j<=n;j++)
    {   if(d[j]==0)
       {    q.push(j); p++; d[j]=p;
            while(!q.empty())
            {   now=q.front();
                z=v[now].size();
                for(i=0;i<z;i++)
                    if(d[v[now][i]]==0)
                    {   d[v[now][i]]=p;
                        q.push(v[now][i]);
                    }
                q.pop();
            }
        }
    }
    g<<p; g.close(); return 0;
}