Cod sursa(job #2313195)

Utilizator RosetiTheodoraFMIUVTRoseti Theodora RosetiTheodoraFMIUVT Data 6 ianuarie 2019 12:30:41
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
int n, m, check[100000], cc=0;
using namespace std;
typedef struct nod
{
	int x;
	nod *pred;
} *pNod;

pNod v[10000];

void addNode(int val, pNod &ultim)
{
	pNod p;
	p = new nod;
	p -> x = val;
	p -> pred = ultim;
	ultim = p;
}

void fileread()
{
	ifstream filein;
    filein.open ("dfs.in");
	filein >> n;
	filein >> m;
	int i, x, y;

	for (i = 1; i <= m; i++)
	{
		filein>>x;
		addNode(y,v[x]);
		filein>>y;
		addNode(x,v[y]);
	}
}

void DFS(int nod)
{
	pNod p;
	check[nod] = 1;
	for (p = v[nod]; p != NULL; p = p -> pred)
        if (check[p -> x]!=NULL)
            DFS(p -> x);
}

int main()
{   ofstream fileout;
    fileout.open ("dfs.out");
	fileread();
	int i;

	for (i = 1; i <= n; i++)
        if (check[i]!=NULL){
             cc++;
            DFS(i);
            }

	fileout<<cc;
	return 0;
}