Cod sursa(job #2501745)

Utilizator Vaida_Radu_AndreiVaida Radu Andrei Vaida_Radu_Andrei Data 30 noiembrie 2019 10:06:07
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <cstdio>
#include <vector>
#include <queue>
#define maxVertices 101024

using namespace std;

int vertices,arces;
int visited[101024],sol;

vector <int> graph[maxVertices];

void addV(int from,int to) {
    graph[from].push_back(to);
}

void read() {
    int i,from,to;
    scanf("%d%d",&vertices,&arces);
    for(i=0;i<arces;++i) {
        scanf("%d%d",&from,&to);
        addV(from,to);
    }
}

void mmset() {
    int i;
    for(i=1;i<=vertices;++i) {
        visited[i]=-1;
    }
}

void fillVertices(int startingVertice) {
    queue <int> lastVisited;
    int pos,i;
    lastVisited.push(startingVertice);
    visited[startingVertice]=0;
    while(!lastVisited.empty()) {
        pos=lastVisited.front();
        lastVisited.pop();
        for(auto&i:graph[pos]) {
            if(visited[i]<0) {
                visited[i]=visited[pos]+1;
                lastVisited.push(i);
            }
        }
    }
}

void solve() {
    int i;
    mmset();
    for(i=1;i<=vertices;++i) {
        if(visited[i]<0) {
            ++sol;
            fillVertices(i);
        }
    }
}

void display() {
    printf("%d",sol);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    read();
    solve();
    display();
    return 0;
}