Cod sursa(job #2084624)

Utilizator andreiionutBude Andrei-Ionut andreiionut Data 9 decembrie 2017 11:09:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
using namespace std;

const int nmax=100001;
int cnt = 0;

ofstream fout("dfs.out");

void ReadGraph(vector<int> G[], int &N, int &M);
void DFS(vector<int>G[], int nod, bool V[]);

int main()
{
int N, M;
bool V[nmax];
for(int i = 1; i <= N; ++i)
V[i] = false;
vector <int> G[nmax];
ReadGraph(G, N, M);
for(int i = 1; i <= N; ++i)
if(V[i] == false)
{
cnt++;
DFS(G, i, V);
}
fout << cnt;
return 0;
}

void ReadGraph(vector<int> G[],int &N,int &M)
{
ifstream fin("dfs.in");
fin >> N >> M;
int x, y;
for(int i = 1; i <= M; ++i)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
}
void DFS(vector<int> G[],int nod,bool V[])
{
V[nod] = true;
for(int i = 0; i < G[nod].size(); ++i)
if(V[G[nod][i]] == false) DFS(G,G[nod][i],V);
}