Cod sursa(job #2049543)

Utilizator ShadowSwangNikola Radulov ShadowSwang Data 27 octombrie 2017 12:47:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

vector <int>G[100001];
ifstream fin;
ofstream fout("dfs.out");
int N,M,Use[100001];

void Read()
{
    int x,y;
    fin.open("dfs.in");
    fin>>N>>M;

    for(int i=1;i<=M;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fin.close();
}

void dfs(int nod, int contor)
{
    Use[nod]=contor;
    for(int i=0;i<G[nod].size();i++)
    {
        if(Use[G[nod][i]]==0)
            dfs(G[nod][i],contor);
    }
}
int main()
{
    int contor=0;
    Read();
    for(int i=1;i<=N;i++)
    {
        if(Use[i]==0)
        {
            contor++;
            dfs(i,contor);
        }
    }
    fout<<contor;
}