Cod sursa(job #1390820)

Utilizator cautionPopescu Teodor caution Data 17 martie 2015 13:00:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <vector>
using namespace std;
vector<long> *graf;
bool *viz;
void dfs(long nod)
{
    for(vector<long>::iterator it=graf[nod].begin(), ed=graf[nod].end(); it!=ed; ++it)
    {
        if(viz[*it]==false)
        {
            viz[*it]=true;
            dfs(*it);
        }
    }
}
int main()
{
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    long n, m, a, b, ctr=0;
    in>>n>>m;
    graf=new vector<long>[n+1];
    viz=new bool[n+1];
    for(long i=1; i<=n; ++i) viz[i]=false;
    for(long i=1; i<=m; ++i)
    {
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    for(long i=1; i<=n; ++i)
    {
        if(viz[i]==0)
        {
            ++ctr;
            dfs(i);
        }
    }
    out<<ctr<<endl;
    in.close(); out.close();
    return 0;
}