Cod sursa(job #1889855)

Utilizator fulger13Pomirleanu Sebastian fulger13 Data 22 februarie 2017 21:53:30
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream q("dfs.in");
ofstream w("dfs.out");

int n,m;
int a[100010];
vector<int> v[100010];
vector<int>::iterator it;
queue<int> c;

void dfs(int s)
{
    int x;
    c.push(s);
    while(!c.empty())
    {
        x=c.front();
        for(it=v[x].begin(); it<v[x].end(); it++)
        {
            if(a[*it]==0)
            {
                a[*it]=1;
                c.push(*it);
            }
        }
        c.pop();
    }
}

int main()
{int i,el=0, x,y;
    q>>n>>m;
    for(i=1;i<=m;i++)
    {
        q>>x>>y;
        v[x].push_back(y);
    }
    for(i=1;i<=n;i++)
    {
        if(a[i]==0) {dfs(i); el++;}
    }
    w<<el;

    return 0;
}