Cod sursa(job #1129678)

Utilizator NitaMihaitavoidcube NitaMihaita Data 28 februarie 2014 01:52:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <vector>
#include <queue>
#define numaru 100001
using namespace std;
vector<int> G[numaru];
int nrarce[numaru];
bool vizitat[numaru];
void DFS(int k)
{
    vizitat[k]=true;
    for(int i=0;i<G[k].size();++i)
        if(!vizitat[G[k][i]]) DFS(G[k][i]);
}
int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int n,m,i,j,nrc=0;
    f>>n>>m;
    for(;m;--m)
    {
        f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    for(i=1;i<=n;++i)
        if(!vizitat[i])
        {
            DFS(i);
            ++nrc;
        }
    g<<nrc<<"\n";
    f.close();
    g.close();
    return 0;
}