Cod sursa(job #994741)

Utilizator StickmanLazar Alexandru Stickman Data 6 septembrie 2013 10:52:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector <int> v[100001];
int n,m,nr;
int c[100001], deg[100001];
bool check[100001];

void dfs(int x)
{
    int i,j,k;
    c[0]=x;
    j=1;
    for(i=0; i<j; i++)
        for(k=0; k<deg[c[i]]; k++)
            if(!check[v[c[i]][k]])
            {
                c[j]=v[c[i]][k];
                check[c[j]]=1;
                j++;
            }
    nr++;
}

int main()
{
    int i,j,x,y;
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    in>>n>>m;
    for(i=0; i<m; i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    in.close();
    for(i=1; i<=n; i++)
        deg[i]=v[i].size();

    for(i=1; i<=n; i++)
        if(!check[i])
            dfs(i);
    out<<nr;
    out.close();
    return 0;

}