Cod sursa(job #2190033)

Utilizator ibogdan25Ilie Ionut ibogdan25 Data 29 martie 2018 17:16:15
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stdio.h>

#define INF 0x7fffffff
#define NMAX 100002

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod {
    int nod;
    int distanta;
	bool operator<(const Nod &o) const
	{
		return distanta > o.distanta;
	}

};
vector < vector < int > > G(NMAX);
vector < int > dist(NMAX, 0);
vector < bool > vizitat(NMAX);
vector < int > cnt_nod_inQ(NMAX, 0);
int n, m, s;

bool compare (const Nod& a, const Nod& b) {
    return a.distanta < b.distanta;
}

void read() {
	FILE * pFile;

	pFile = fopen("dfs.in", "r");
    //f >> n >> m;
	fscanf(pFile, "%d %d", &n, &m);
	int x = 0, y = 0, dist = 0;
	Nod nod_pereche;
    while (m--) {
		fscanf(pFile, "%d %d", &x, &y);

		G[x].push_back(y);
    }
}
Nod constructNode(int nod, int distanta) {
	Nod new_node;
	new_node.nod = nod;
	new_node.distanta = distanta;
	return new_node;
}
void bfs(int nodSursa) {
    queue<int> qNode;
    qNode.push(nodSursa);
    vizitat[nodSursa] = true;
    while (!qNode.empty()) {
        int nod = qNode.front();
        qNode.pop();
        for (int i = 0; i < G[nod].size(); i++) {
            int nodVecin = G[nod][i];
            if (!vizitat[nodVecin]) {
                vizitat[nodVecin] = true;
                dist[nodVecin] = dist[nod] + 1;
                qNode.push(nodVecin);
            }
        }
    }
}
int main()
{
    read();
    int counter = 0;
    for (int i = 1; i <= n; i++) {
        if (!vizitat[i]) {
            counter++;
            bfs(i);
        }
    }
    FILE * pFile;

	pFile = fopen("dfs.out", "w");
    fprintf(pFile, "%d", counter);

    return 0;
}