Cod sursa(job #2313288)

Utilizator RosetiTheodoraFMIUVTRoseti Theodora RosetiTheodoraFMIUVT Data 6 ianuarie 2019 16:24:19
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
int n, m, check[100000];
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>>y;
		filein>>x;
		addNode(y,v[x]);

		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]==0)
            DFS(p -> x);
}

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

	for (i = 1; i <= n; i++){

        if (check[i]==0)
             cc++;
             DFS(i);
            }
    cout<<cc;
	//fileout<<cc;
	return 0;
}