Cod sursa(job #592431)

Utilizator blastoiseZ.Z.Daniel blastoise Data 28 mai 2011 13:09:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstring>
#include <vector>

#define MAX 100001

using namespace std;

int N,sol=0;
int use[MAX];
vector <int> v[MAX];

inline void Read()
{
    int M,x,y;
    ifstream in;

    in.open("dfs.in");

    in>>N>>M;
    for(;M;--M)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    in.close();
}

inline void df(int nod)
{
    vector <int>::iterator it;

    use[nod]=1;
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(!use[*it]) df(*it);
}

inline void DFS()
{
    for(int i=1;i<=N;i++)
        if(!use[i])
        {
            df(i);
            sol++;
        }
}

inline void Write()
{
    ofstream out;

    out.open("dfs.out");

    out<<sol<<'\n';

    out.close();
}

int main()
{
    Read();
    DFS();
    Write();

    return 0;
}